輸入一個×××數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)，數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有和。
求所有子數(shù)組的和的最大值。要求時間復(fù)雜度為O(n)。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，因此輸出為該子數(shù)組的和18。

創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站制作、做網(wǎng)站、仙居網(wǎng)絡(luò)推廣、小程序開發(fā)、仙居網(wǎng)絡(luò)營銷、仙居企業(yè)策劃、仙居品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎；創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供仙居建站搭建服務(wù)，24小時服務(wù)熱線：13518219792，官方網(wǎng)址：www.cdcxhl.com

    因為這個要求的時間復(fù)雜度為O(n)，所以數(shù)組只能遍歷一遍，因此這個代碼的主要思想在于，先給定max為a[0]，然后判斷后面的數(shù)組相加是否大于max，如果大于就賦值給max，因為任何數(shù)加上負(fù)數(shù)都會變小，所以只要sum的值小于0，都讓它賦值為0，意思就是拋棄前面所加的數(shù)，然后再進(jìn)行sum的運(yùn)算。

    這個方法，也適合數(shù)組內(nèi)全是負(fù)數(shù)的情況，如果哪位大神發(fā)現(xiàn)了bug歡迎私聊。

#include

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;

}