一、問題描述
輸入一個整形數組，數組裡可以有正數或負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求時間復雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，因此輸出為該子數組的和18。
第一次遇到這道題是參加x迅的筆試。題目中給出了兩種解法，讓填空。
二、簡單解
拿到這道題，如果不考慮性能和復雜度，最簡單的方法就是窮舉。窮舉出所有的子數組，並求出他們的和，返回最大值。不過，復雜度為O(n3)，不符合題目的要求（復雜度On）
[cpp] view plaincopyprint?
int max_sum(int *arr, int len){
int max, sum;
for(int i = 0; i < len; i++) {
for(int j = i; j < len; j++) {
sum = 0;
for(int k = i; k <= j; k++) {
sum = sum + arr[k];
if(sum > max) {
max = sum;
}
}
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
int max_sum(int *arr, int len){
int max, sum;
for(int i = 0; i < len; i++) {
for(int j = i; j < len; j++) {
sum = 0;
for(int k = i; k <= j; k++) {
sum = sum + arr[k];
if(sum > max) {
max = sum;
}
}
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
三、復雜度為N2的解
觀察上面的代碼，我們使用了3個for循環。其中最內側的for循環主要是控制每個字序列的長度，由於我們在計算的過程中，已經保存了當前最大字序列和，字序列的長度N對我們來說意義不大，因此完全可以撤消最內側的循環。只按每個字序列起始位置來計算最大和。這樣得到一個復雜度為N2的解。
[cpp] view plaincopyprint?
int max_sum2(int *arr, int len){
int sum, max = 0;
for(int i = 0; i < len; i++) {
sum = 0;
for(int j = i; j < len; j++) {
sum = sum + arr[j];
if(max < sum) {
max = sum;
}
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
int max_sum2(int *arr, int len){
int sum, max = 0;
for(int i = 0; i < len; i++) {
sum = 0;
for(int j = i; j < len; j++) {
sum = sum + arr[j];
if(max < sum) {
max = sum;
}
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
四、更低復雜度的探索
至此，我們已經得到一個復雜度為N2的解法。那麼有沒有更低復雜度的算法呢？在N2的算法中，我們遍歷了從0到len-1開始的字序列，求出每種情況下得到的最大字序列和。那麼我們有沒有可能去掉這個循環呢？考慮使用動態規劃的思想，記max_sum[i]為從0到i的子序列的最大和，那麼可以得到遞推式：
[cpp] view plaincopyprint?
if max_sum[i] > 0
then
if arr[i+1] > 0
then max_sum[i+1] = max_sum[i] + arr[i+1];
else
max_sum[i+1] = max(0, arr[i+1])
if max_sum[i] > 0
then
if arr[i+1] > 0
then max_sum[i+1] = max_sum[i] + arr[i+1];
else
max_sum[i+1] = max(0, arr[i+1])
利用這種思路得到一個線性時間的解答：
[cpp] view plaincopyprint?
int max_sum3(int *arr, int len) {
int sum, max;
max = sum = 0;
for(int i = 0; i < len; i++) {
sum += arr[i];
if(sum < 0) {
sum = 0;
}
if(sum > max){
max = sum;
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
int max_sum3(int *arr, int len) {
int sum, max;
max = sum = 0;
for(int i = 0; i < len; i++) {
sum += arr[i];
if(sum < 0) {
sum = 0;
}
if(sum > max){
max = sum;
}
}
if(max == 0) {
return max(arr, len);
}
return max;
}
至此，我們得到一個時間復雜度On，空間復雜度O1的解。
