輸入一個×××數組，數組里有正數也有負數，數組中連續的一個或多個整數組成一個子數組，每個子數組都有和。
求所有子數組的和的最大值。要求時間復雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，因此輸出為該子數組的和18。
因為這個要求的時間復雜度為O(n)，所以數組只能遍歷一遍，因此這個代碼的主要思想在于，先給定max為a[0]，然后判斷后面的數組相加是否大于max，如果大于就賦值給max，因為任何數加上負數都會變小，所以只要sum的值小于0，都讓它賦值為0，意思就是拋棄前面所加的數，然后再進行sum的運算。
這個方法，也適合數組內全是負數的情況，如果哪位大神發現了bug歡迎私聊。
#include<stdio.h>
int main()
{
int a[8] = {-2, 5, 4, -5, 9, 0, 1, -2};
int max = a[0];
int sum = 0;
int i = 0;
for (i-0; i<8; i++){
sum += a[i];
if(max < sum)
max = sum;
if(sum < 0)
sum = 0;
}
printf("max: %d\n", max);
return 0;
}
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
