## 題目描述 輸入一個整形數組，數組里有正數也有負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。 求所有子數組的和的最大值，要求時間復雜度為O(n)。 例如輸入的數組為`1, -2, 3, 10, -4, 7, 2, -5`，和最大的子數組為`3, 10, -4, 7, 2`， 因此輸出為該子數組的和18。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#分析與解法)分析與解法 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#解法一)解法一 求一個數組的最大子數組和，我想最直觀最野蠻的辦法便是，三個for循環三層遍歷，求出數組中每一個子數組的和，最終求出這些子數組的最大的一個值。 令currSum[i, …, j]為數組A中第i個元素到第j個元素的和（其中0 <= i <= j < n），maxSum為最終求到的最大連續子數組的和。 且當全是負數的情況時，我們可以讓程序返回0，也可以讓程序返回最大的那個負數，這里，我們讓程序返回最大的那個負數。 參考代碼如下： ~~~ int MaxSubArray(int* A, int n) { int maxSum = a[0]; //全負情況，返回最大負數 int currSum = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { for (int k = i; k <= j; k++) { currSum += A[k]; } if (currSum > maxSum) maxSum = currSum; currSum = 0; //這里要記得清零，否則的話sum最終存放的是所有子數組的和。 } } return maxSum; } ~~~ 此方法的時間復雜度為O(n^3)。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#解法二)解法二 事實上，當我們令currSum為當前最大子數組的和，maxSum為最后要返回的最大子數組的和，當我們往后掃描時， * 對第j+1個元素有兩種選擇：要么放入前面找到的子數組，要么做為新子數組的第一個元素； * 如果currSum加上當前元素a[j]后不小于a[j]，則令currSum加上a[j]，否則currSum重新賦值，置為下一個元素，即currSum = a[j]。 * 同時，當currSum > maxSum，則更新maxSum = currSum，否則保持原值，不更新。 即 ~~~ currSum = max(a[j], currSum + a[j]) maxSum = max(maxSum, currSum) ~~~ 舉個例子，當輸入數組是`1, -2, 3, 10, -4, 7, 2, -5`，那么，currSum和maxSum相應的變化為： * currSum： 0 1 - 1 3 13 9 16 18 13 * maxSum ： 0 1 1 3 13 13 16 18 18 參考代碼如下： ~~~ int MaxSubArray(int* a, int n) { int currSum = 0; int maxSum = a[0]; //全負情況，返回最大數 for (int j = 0; j < n; j++) { currSum = (a[j] > currSum + a[j]) ? a[j] : currSum + a[j]; maxSum = (maxSum > currSum) ? maxSum : currSum; } return maxSum; } ~~~ ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#問題擴展)問題擴展 1. 如果數組是二維數組，同樣要你求最大子數組的和列? 2. 如果是要你求子數組的最大乘積列? 3. 如果同時要求輸出子段的開始和結束列? ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md#舉一反三)舉一反三 1 給定整型數組，其中每個元素表示木板的高度，木板的寬度都相同，求這些木板拼出的最大矩形的面積。并分析時間復雜度。 此題類似leetcode里面關于連通器的題，需要明確的是高度可能為0，長度最長的矩形并不一定是最大矩形，還需要考慮高度很高，但長度較短的矩形。如[5,4,3,2,4,5,0,7,8,4,6]中最大矩形的高度是[7,8,4,6]組成的矩形，面積為16。 2、環面上的最大子矩形 《算法競賽入門經典》 P89 頁。 3、最大子矩陣和 一個M_N的矩陣，找到此矩陣的一個子矩陣，并且這個子矩陣的元素的和是最大的，輸出這個最大的值。如果所有數都是負數，就輸出0。 例如：3_5的矩陣： 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 和最大的子矩陣是： 4 5 5 3 最后輸出和的最大值17。 4、允許交換兩個數的位置 求最大子數組和。 來源：[https://codility.com/cert/view/certDUMWPM-8RF86G8P9QQ6JC8X/details](https://codility.com/cert/view/certDUMWPM-8RF86G8P9QQ6JC8X/details)?。