對象允許存儲鍵值集合，這很好。

但很多時候我們發(fā)現(xiàn)還需要 有序集合，里面的元素都是按順序排列的。例如，我們可能需要存儲一些列表，比如用戶、商品以及 HTML 元素等。

使用對象就不是很方便了，因為對象不能提供能夠管理元素順序的方法。我們不能在已有的元素“之間”插入一個新的屬性。這種場景下對象就不太適用了。

這時一個特殊的數(shù)據(jù)結(jié)構(gòu)數(shù)組（Array）就派上用場了，它能存儲有序的集合。

聲明

創(chuàng)建一個空數(shù)組有兩種語法：

let arr = new Array();
let arr = [];

絕大多數(shù)情況下使用的都是第二種語法。我們可以在方括號中添加初始元素：

let fruits = ["Apple", "Orange", "Plum"];

數(shù)組元素從 0 開始編號。

我們可以通過方括號中的數(shù)字獲取元素：

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits[0] ); // Apple
alert( fruits[1] ); // Orange
alert( fruits[2] ); // Plum

可以替換元素：

fruits[2] = 'Pear'; // 現(xiàn)在變成了 ["Apple", "Orange", "Pear"]

……或者向數(shù)組新加一個元素：

fruits[3] = 'Lemon'; // 現(xiàn)在變成 ["Apple", "Orange", "Pear", "Lemon"]

length 屬性的值是數(shù)組中元素的總個數(shù)：

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits.length ); // 3

也可以用 ?alert ?來顯示整個數(shù)組。

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits ); // Apple,Orange,Plumlet fruits = ["Apple", "Orange", "Plum"];

alert( fruits ); // Apple,Orange,Plum

數(shù)組可以存儲任何類型的元素。

例如：

// 混合值
let arr = [ 'Apple', { name: 'John' }, true, function() { alert('hello'); } ];

// 獲取索引為 1 的對象然后顯示它的 name
alert( arr[1].name ); // John

// 獲取索引為 3 的函數(shù)并執(zhí)行
arr[3](); // hello

以逗號結(jié)尾

數(shù)組就像對象一樣，可以以逗號結(jié)尾：

let fruits = [
  "Apple",
  "Orange",
  "Plum",
];

因為每一行都是相似的，所以這種以“逗號結(jié)尾”的方式使得插入/移除項變得更加簡單。

使用 “at” 獲取最后一個元素

最近新增的特性

這是一個最近添加到 JavaScript 的特性。 舊式瀏覽器可能需要 polyfills.

假設(shè)我們想要數(shù)組的最后一個元素。

一些編程語言允許我們使用負數(shù)索引來實現(xiàn)這一點，例如 fruits[-1]。

但在 JavaScript 中這行不通。結(jié)果將是 undefined，因為方括號中的索引是被按照其字面意思處理的。

我們可以顯式地計算最后一個元素的索引，然后訪問它：fruits[fruits.length - 1]。

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits[fruits.length-1] ); // Plum

有點麻煩，不是嗎？我們需要寫兩次變量名。

幸運的是，這里有一個更簡短的語法 fruits.at(-1)：

let fruits = ["Apple", "Orange", "Plum"];

// 與 fruits[fruits.length-1] 相同
alert( fruits.at(-1) ); // Plum

換句話說，arr.at(i)：

• 如果 ?i >= 0?，則與 ?arr[i]? 完全相同。
• 對于 ?i? 為負數(shù)的情況，它則從數(shù)組的尾部向前數(shù)。

pop/push, shift/unshift 方法

隊列（queue）是最常見的使用數(shù)組的方法之一。在計算機科學(xué)中，這表示支持兩個操作的一個有序元素的集合：

• ?push ?在末端添加一個元素.
• ?shift ?取出隊列首端的一個元素，整個隊列往前移，這樣原先排第二的元素現(xiàn)在排在了第一。

這兩種操作數(shù)組都支持。

隊列的應(yīng)用在實踐中經(jīng)常會碰到。例如需要在屏幕上顯示消息隊列。

數(shù)組還有另一個用例，就是數(shù)據(jù)結(jié)構(gòu) 棧。

它支持兩種操作：

• ?push ?在末端添加一個元素.
• ?pop ?從末端取出一個元素.

所以新元素的添加和取出都是從“末端”開始的。

棧通常被被形容成一疊卡片：要么在最上面添加卡片，要么從最上面拿走卡片：

對于棧來說，最后放進去的內(nèi)容是最先接收的，也叫做 LIFO（Last-In-First-Out），即后進先出法則。而與隊列相對應(yīng)的叫做 FIFO（First-In-First-Out），即先進先出。

JavaScript 中的數(shù)組既可以用作隊列，也可以用作棧。它們允許你從首端/末端來添加/刪除元素。

這在計算機科學(xué)中，允許這樣的操作的數(shù)據(jù)結(jié)構(gòu)被稱為 雙端隊列（deque）。

作用于數(shù)組末端的方法：

?pop?

取出并返回數(shù)組的最后一個元素：

let fruits = ["Apple", "Orange", "Pear"];

alert( fruits.pop() ); // 移除 "Pear" 然后 alert 顯示出來

alert( fruits ); // Apple, Orange

fruits.pop() 和 fruits.at(-1) 都返回數(shù)組的最后一個元素，但 fruits.pop() 同時也刪除了數(shù)組的最后一個元素，進而修改了原數(shù)組。

?push
?

在數(shù)組末端添加元素：

let fruits = ["Apple", "Orange"];

fruits.push("Pear");

alert( fruits ); // Apple, Orange, Pear

調(diào)用 fruits.push(...) 與 fruits[fruits.length] = ... 是一樣的。

作用于數(shù)組首端的方法：

?shift?

取出數(shù)組的第一個元素并返回它：

let fruits = ["Apple", "Orange", "Pear"];

alert( fruits.shift() ); // 移除 Apple 然后 alert 顯示出來

alert( fruits ); // Orange, Pear

?unshift?

在數(shù)組的首端添加元素：

let fruits = ["Orange", "Pear"];

fruits.unshift('Apple');

alert( fruits ); // Apple, Orange, Pear

push 和 unshift 方法都可以一次添加多個元素：

let fruits = ["Apple"];

fruits.push("Orange", "Peach");
fruits.unshift("Pineapple", "Lemon");

// ["Pineapple", "Lemon", "Apple", "Orange", "Peach"]
alert( fruits );

內(nèi)部

數(shù)組是一種特殊的對象。使用方括號來訪問屬性 arr[0] 實際上是來自于對象的語法。它其實與 obj[key] 相同，其中 arr 是對象，而數(shù)字用作鍵（key）。

它們擴展了對象，提供了特殊的方法來處理有序的數(shù)據(jù)集合以及 length 屬性。但從本質(zhì)上講，它仍然是一個對象。

記住，在 JavaScript 中只有 8 種基本的數(shù)據(jù)類型（詳見 數(shù)據(jù)類型 一章）。數(shù)組是一個對象，因此其行為也像一個對象。

例如，它是通過引用來復(fù)制的：

let fruits = ["Banana"]

let arr = fruits; // 通過引用復(fù)制 (兩個變量引用的是相同的數(shù)組)

alert( arr === fruits ); // true

arr.push("Pear"); // 通過引用修改數(shù)組

alert( fruits ); // Banana, Pear — 現(xiàn)在有 2 項了

……但是數(shù)組真正特殊的是它們的內(nèi)部實現(xiàn)。JavaScript 引擎嘗試把這些元素一個接一個地存儲在連續(xù)的內(nèi)存區(qū)域，就像本章的插圖顯示的一樣，而且還有一些其它的優(yōu)化，以使數(shù)組運行得非常快。

但是，如果我們不像“有序集合”那樣使用數(shù)組，而是像常規(guī)對象那樣使用數(shù)組，這些就都不生效了。

例如，從技術(shù)上講，我們可以這樣做:

let fruits = []; // 創(chuàng)建一個數(shù)組

fruits[99999] = 5; // 分配索引遠大于數(shù)組長度的屬性

fruits.age = 25; // 創(chuàng)建一個具有任意名稱的屬性

這是可以的，因為數(shù)組是基于對象的。我們可以給它們添加任何屬性。

但是 Javascript 引擎會發(fā)現(xiàn)，我們在像使用常規(guī)對象一樣使用數(shù)組，那么針對數(shù)組的優(yōu)化就不再適用了，然后對應(yīng)的優(yōu)化就會被關(guān)閉，這些優(yōu)化所帶來的優(yōu)勢也就蕩然無存了。

數(shù)組誤用的幾種方式:

• 添加一個非數(shù)字的屬性，比如 ?arr.test = 5?。
• 制造空洞，比如：添加 ?arr[0]?，然后添加 ?arr[1000]? (它們中間什么都沒有)。
• 以倒序填充數(shù)組，比如 ?arr[1000]?，?arr[999]? 等等。

請將數(shù)組視為作用于 有序數(shù)據(jù) 的特殊結(jié)構(gòu)。它們?yōu)榇颂峁┝颂厥獾姆椒?。?shù)組在 JavaScript 引擎內(nèi)部是經(jīng)過特殊調(diào)整的，使得更好地作用于連續(xù)的有序數(shù)據(jù)，所以請以正確的方式使用數(shù)組。如果你需要任意鍵值，那很有可能實際上你需要的是常規(guī)對象 {}。

性能

push/pop 方法運行的比較快，而 shift/unshift 比較慢。

為什么作用于數(shù)組的末端會比首端快呢？讓我們看看在執(zhí)行期間都發(fā)生了什么：

fruits.shift(); // 從首端取出一個元素

只獲取并移除索引 0 對應(yīng)的元素是不夠的。其它元素也需要被重新編號。

shift 操作必須做三件事：

1. 移除索引為 ?0? 的元素。
2. 把所有的元素向左移動，把索引 ?1? 改成 ?0?，?2? 改成 ?1? 以此類推，對其重新編號。
3. 更新 ?length ?屬性。

數(shù)組里的元素越多，移動它們就要花越多的時間，也就意味著越多的內(nèi)存操作。

unshift 也是一樣：為了在數(shù)組的首端添加元素，我們首先需要將現(xiàn)有的元素向右移動，增加它們的索引值。

那 push/pop 是什么樣的呢？它們不需要移動任何東西。如果從末端移除一個元素，pop 方法只需要清理索引值并縮短 length 就可以了。

pop 操作的行為：

fruits.pop(); // 從末端取走一個元素

pop 方法不需要移動任何東西，因為其它元素都保留了各自的索引。這就是為什么 pop 會特別快。

push 方法也是一樣的。

循環(huán)

遍歷數(shù)組最古老的方式就是 for 循環(huán)：

let arr = ["Apple", "Orange", "Pear"];

for (let i = 0; i < arr.length; i++) {
  alert( arr[i] );
}

但對于數(shù)組來說還有另一種循環(huán)方式，for..of：

let fruits = ["Apple", "Orange", "Plum"];

// 遍歷數(shù)組元素
for (let fruit of fruits) {
  alert( fruit );
}

for..of 不能獲取當前元素的索引，只是獲取元素值，但大多數(shù)情況是夠用的。而且這樣寫更短。

技術(shù)上來講，因為數(shù)組也是對象，所以使用 for..in 也是可以的：

let arr = ["Apple", "Orange", "Pear"];

for (let key in arr) {
  alert( arr[key] ); // Apple, Orange, Pear
}

但這其實是一個很不好的想法。會有一些潛在問題存在：

1. ?for..in? 循環(huán)會遍歷 所有屬性，不僅僅是這些數(shù)字屬性。

在瀏覽器和其它環(huán)境中有一種稱為“類數(shù)組”的對象，它們 看似是數(shù)組。也就是說，它們有 length 和索引屬性，但是也可能有其它的非數(shù)字的屬性和方法，這通常是我們不需要的。for..in 循環(huán)會把它們都列出來。所以如果我們需要處理類數(shù)組對象，這些“額外”的屬性就會存在問題。


2. ?for..in? 循環(huán)適用于普通對象，并且做了對應(yīng)的優(yōu)化。但是不適用于數(shù)組，因此速度要慢 10-100 倍。當然即使是這樣也依然非?？臁Ｖ挥性谟龅狡款i時可能會有問題。但是我們?nèi)匀粦?yīng)該了解這其中的不同。

通常來說，我們不應(yīng)該用 for..in 來處理數(shù)組。

關(guān)于 “l(fā)ength”

當我們修改數(shù)組的時候，length 屬性會自動更新。準確來說，它實際上不是數(shù)組里元素的個數(shù)，而是最大的數(shù)字索引值加一。

例如，一個數(shù)組只有一個元素，但是這個元素的索引值很大，那么這個數(shù)組的 length 也會很大：

let fruits = [];
fruits[123] = "Apple";

alert( fruits.length ); // 124

要知道的是我們通常不會這樣使用數(shù)組。

length 屬性的另一個有意思的點是它是可寫的。

如果我們手動增加它，則不會發(fā)生任何有趣的事兒。但是如果我們減少它，數(shù)組就會被截斷。該過程是不可逆的，下面是例子：

let arr = [1, 2, 3, 4, 5];

arr.length = 2; // 截斷到只剩 2 個元素
alert( arr ); // [1, 2]

arr.length = 5; // 又把 length 加回來
alert( arr[3] ); // undefined：被截斷的那些數(shù)值并沒有回來

所以，清空數(shù)組最簡單的方法就是：arr.length = 0;。

new Array()

這是創(chuàng)建數(shù)組的另一種語法：

let arr = new Array("Apple", "Pear", "etc");

它很少被使用，因為方括號 [] 更短更簡潔。而且，這種語法還有一個棘手的特性。

如果使用單個參數(shù)（即數(shù)字）調(diào)用 new Array，那么它會創(chuàng)建一個 指定了長度，卻沒有任何項 的數(shù)組。

讓我們看看如何搬起石頭砸自己的腳:

let arr = new Array(2); // 會創(chuàng)建一個 [2] 的數(shù)組嗎？

alert( arr[0] ); // undefined！沒有元素。

alert( arr.length ); // length 2

為了避免這種意外情況，我們通常使用方括號，除非我們真的知道自己在做什么。

多維數(shù)組

數(shù)組里的項也可以是數(shù)組。我們可以將其用于多維數(shù)組，例如存儲矩陣：

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

alert( matrix[1][1] ); // 最中間的那個數(shù)

toString

數(shù)組有自己的 toString 方法的實現(xiàn)，會返回以逗號隔開的元素列表。

例如：

let arr = [1, 2, 3];

alert( arr ); // 1,2,3
alert( String(arr) === '1,2,3' ); // true

此外，我們試試運行一下這個：

alert( [] + 1 ); // "1"
alert( [1] + 1 ); // "11"
alert( [1,2] + 1 ); // "1,21"

數(shù)組沒有 Symbol.toPrimitive，也沒有 valueOf，它們只能執(zhí)行 toString 進行轉(zhuǎn)換，所以這里 [] 就變成了一個空字符串，[1] 變成了 "1"，[1,2] 變成了 "1,2"。

當 "+" 運算符把一些項加到字符串后面時，加號后面的項也會被轉(zhuǎn)換成字符串，所以下一步就會是這樣：

alert( "" + 1 ); // "1"
alert( "1" + 1 ); // "11"
alert( "1,2" + 1 ); // "1,21"

不要使用 == 比較數(shù)組

JavaScript 中的數(shù)組與其它一些編程語言的不同，不應(yīng)該使用 == 運算符比較 JavaScript 中的數(shù)組。

該運算符不會對數(shù)組進行特殊處理，它會像處理任意對象那樣處理數(shù)組。

讓我們回顧一下規(guī)則：

• 僅當兩個對象引用的是同一個對象時，它們才相等 ?==?。
• 如果 ?==? 左右兩個參數(shù)之中有一個參數(shù)是對象，另一個參數(shù)是原始類型，那么該對象將會被轉(zhuǎn)換為原始類型，轉(zhuǎn)換規(guī)則如 對象 —— 原始值轉(zhuǎn)換 一章所述。
• ……?null ?和 ?undefined ?相等 ?==?，且各自不等于任何其他的值。

嚴格比較 === 更簡單，因為它不會進行類型轉(zhuǎn)換。

所以，如果我們使用 == 來比較數(shù)組，除非我們比較的是兩個引用同一數(shù)組的變量，否則它們永遠不相等。

例如：

alert( [] == [] ); // false
alert( [0] == [0] ); // false

從技術(shù)上講，這些數(shù)組是不同的對象。所以它們不相等。== 運算符不會進行逐項比較。

與原始類型的比較也可能會產(chǎn)生看似很奇怪的結(jié)果：

alert( 0 == [] ); // true

alert('0' == [] ); // false

在這里的兩個例子中，我們將原始類型和數(shù)組對象進行比較。因此，數(shù)組 [] 被轉(zhuǎn)換為原始類型以進行比較，被轉(zhuǎn)換成了一個空字符串 ''。

然后，接下來的比較就是原始類型之間的比較，如 類型轉(zhuǎn)換 一章所述：

// 在 [] 被轉(zhuǎn)換為 '' 后
alert( 0 == '' ); // true，因為 '' 被轉(zhuǎn)換成了數(shù)字 0

alert('0' == '' ); // false，沒有進一步的類型轉(zhuǎn)換，是不同的字符串

那么，我們應(yīng)該如何對數(shù)組進行比較呢？

很簡單，不要使用 == 運算符。而是，可以在循環(huán)中或者使用下一章中我們將介紹的迭代方法逐項地比較它們。

總結(jié)

數(shù)組是一種特殊的對象，適用于存儲和管理有序的數(shù)據(jù)項。

聲明：

// 方括號 (常見用法)
let arr = [item1, item2...];

// new Array (極其少見)
let arr = new Array(item1, item2...);

調(diào)用 new Array(number) 會創(chuàng)建一個給定長度的數(shù)組，但不含有任何項。

• ?length ?屬性是數(shù)組的長度，準確地說，它是數(shù)組最后一個數(shù)字索引值加一。它由數(shù)組方法自動調(diào)整。
• 如果我們手動縮短 ?length?，那么數(shù)組就會被截斷。

獲取元素：

• 你可以通過元素的索引獲取元素，例如 ?arr[0]?
• 我們也可以使用允許負索引的 ?at(i)? 方法。對于負值的 ?i?，它會從數(shù)組的末尾往回數(shù)。如果 ?i >= 0?，它的工作方式與 ?arr[i]? 相同。

我們可以通過下列操作以雙端隊列的方式使用數(shù)組：

• ?push(...items)? 在末端添加 ?items ?項。
• ?pop()? 從末端移除并返回該元素。
• ?shift()? 從首端移除并返回該元素。
• ?unshift(...items)? 從首端添加 ?items ?項。

遍歷數(shù)組的元素：

• ?for (let i=0; i<arr.length; i++)? — 運行得最快，可兼容舊版本瀏覽器。
• ?for (let item of arr)? — 現(xiàn)代語法，只能訪問 items。
• ?for (let i in arr)? — 永遠不要用這個。

比較數(shù)組時，不要使用 == 運算符（當然也不要使用 > 和 < 等運算符），因為它們不會對數(shù)組進行特殊處理。它們通常會像處理任意對象那樣處理數(shù)組，這通常不是我們想要的。

但是，我們可以使用 for..of 循環(huán)來逐項比較數(shù)組。

在下一章 數(shù)組方法 中，我們將繼續(xù)學(xué)習(xí)數(shù)組，學(xué)習(xí)更多添加、移除、提取元素和數(shù)組排序的方法。

任務(wù)

---

數(shù)組被拷貝了嗎?

重要程度: 3

下面的代碼將會顯示什么？

let fruits = ["Apples", "Pear", "Orange"];

// 在“副本”里 push 了一個新的值
let shoppingCart = fruits;
shoppingCart.push("Banana");

// fruits 里面是什么？
alert( fruits.length ); // ?

---

解決方案

結(jié)果是 4:

let fruits = ["Apples", "Pear", "Orange"];

let shoppingCart = fruits;

shoppingCart.push("Banana");

alert( fruits.length ); // 4

這是因為數(shù)組是對象。所以 shoppingCart 和 fruits 是同一數(shù)組的引用。

---

數(shù)組操作。

重要程度: 5

我們試試下面的 5 個數(shù)組操作。

1. 創(chuàng)建一個數(shù)組 ?styles?，里面存儲有 “Jazz” 和 “Blues”。
2. 將 “Rock-n-Roll” 從數(shù)組末端添加進去。
3. 用 “Classics” 替換掉數(shù)組最中間的元素。查找數(shù)組最中間的元素的代碼應(yīng)該適用于任何奇數(shù)長度的數(shù)組。
4. 去掉數(shù)組的第一個值并顯示它。
5. 在數(shù)組前面添加 ?Rap ?和 ?Reggae?。

過程中的數(shù)組：

Jazz, Blues
Jazz, Blues, Rock-n-Roll
Jazz, Classics, Rock-n-Roll
Classics, Rock-n-Roll
Rap, Reggae, Classics, Rock-n-Roll

---

解決方案

let styles = ["Jazz", "Blues"];
styles.push("Rock-n-Roll");
styles[Math.floor((styles.length - 1) / 2)] = "Classics";
alert( styles.shift() );
styles.unshift("Rap", "Reggae");

---

在數(shù)組上下文調(diào)用

重要程度: 5

結(jié)果是什么？為什么？

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
});

arr[2](); // ?

---

解決方案

arr[2]() 調(diào)用從句法來看可以類比于 obj[method]()，與 obj 對應(yīng)的是 arr，與 method 對應(yīng)的是 2。

所以調(diào)用 arr[2] 函數(shù)也就是調(diào)用對象函數(shù)。自然地，它接收 this 引用的對象 arr 然后輸出該數(shù)組：

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // a,b,function(){...}

該數(shù)組有 3 項：最開始有兩個，后來添加進來一個函數(shù)。

---

輸入數(shù)字求和

重要程度: 4

寫出函數(shù) sumInput()，要求如下：

• 使用 ?prompt ?向用戶索要值，并存在數(shù)組中。
• 當用戶輸入了非數(shù)字、空字符串或者點擊“取消”按鈕的時候，問詢結(jié)束。
• 計算并返回數(shù)組所有項之和。

P.S. ?0? 是有效的數(shù)字，不要因為是 0 就停止問詢。

---

解決方案

請注意這個解決方案的細微但是很重要的細節(jié)。我們沒有在 prompt 后立即把 value 轉(zhuǎn)換成數(shù)字，因為在執(zhí)行 value = +value 之后，就沒辦法區(qū)分出空字符串（中斷標志）和數(shù)字 0（合法輸入）了，所以要放到后面再處理。

function sumInput() {

  let numbers = [];

  while (true) {

    let value = prompt("A number please?", 0);

    // 應(yīng)該結(jié)束了嗎？
    if (value === "" || value === null || !isFinite(value)) break;

    numbers.push(+value);
  }

  let sum = 0;
  for (let number of numbers) {
    sum += number;
  }
  return sum;
}

alert( sumInput() );

---

最大子數(shù)組

重要程度: 2

輸入是以數(shù)字組成的數(shù)組，例如 arr = [1, -2, 3, 4, -9, 6].

任務(wù)是：找出所有項的和最大的 arr 數(shù)組的連續(xù)子數(shù)組。

寫出函數(shù) getMaxSubSum(arr)，用其找出并返回最大和。

例如：

getMaxSubSum([-1, 2, 3, -9]) == 5（高亮項的加和）
getMaxSubSum([2, -1, 2, 3, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, 11]) == 11
getMaxSubSum([-2, -1, 1, 2]) == 3
getMaxSubSum([100, -9, 2, -3, 5]) == 100
getMaxSubSum([1, 2, 3]) == 6（所有項的和）

如果所有項都是負數(shù)，那就一個項也不取（子數(shù)組是空的），所以返回的是 0：

getMaxSubSum([-1, -2, -3]) = 0

請嘗試想出一個快速的解決方案：復(fù)雜度可以是 O(n²)，有能力達到 O(n) 則更好。

---

解決方案

慢的解決方案

我們可以計算所有可能的子集的和。

最簡單的方法就是獲取每個元素然后計算從它開始所有子數(shù)組的和。

以 [-1, 2, 3, -9, 11] 為例：

// 從 -1 開始：
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// 從 2 開始：
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// 從 3 開始：
3
3 + (-9)
3 + (-9) + 11

// 從 -9 開始：
-9
-9 + 11

// 從 11 開始：
11

這樣寫出來的代碼實際上是一個嵌套循環(huán)：外部循環(huán)遍歷數(shù)組所有元素，內(nèi)部循環(huán)計算從當前元素開始的所有子數(shù)組各自的和。

function getMaxSubSum(arr) {
  let maxSum = 0; // 如果沒有取到任何元素，就返回 0

  for (let i = 0; i < arr.length; i++) {
    let sumFixedStart = 0;
    for (let j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

該方案的時間復(fù)雜度是 O(n²)。也就是說，如果我們把數(shù)組大小增加 2 倍，那么算法的運行時間將會延長4倍。

對于大型數(shù)組（1000，10000 或者更多項）這種算法會導(dǎo)致嚴重的時間消耗。

快的解決方案

讓我們遍歷數(shù)組，將當前局部元素的和保存在變量 s 中。如果 s 在某一點變成負數(shù)了，就重新分配 s=0。所有 s 中的最大值就是答案。

如果文字描述不太好理解，就直接看下面的代碼吧，真的很短：

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) { // arr 中的每個 item
    partialSum += item; // 將其加到 partialSum
    maxSum = Math.max(maxSum, partialSum); // 記住最大值
    if (partialSum < 0) partialSum = 0; // 如果是負數(shù)就置為 0
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0

該算法只需要遍歷 1 輪數(shù)組，所以時間復(fù)雜度是 O(n)。

你也可以在這獲取更多該算法的細節(jié)信息：最大子數(shù)組問題。如果還是不明白，那就調(diào)試上面的例子，觀察它是怎樣工作的，說得再多也沒有自己去調(diào)試好使。

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) {
    partialSum += item;
    maxSum = Math.max(maxSum, partialSum);
    if (partialSum < 0) partialSum = 0;
  }
  return maxSum;
}