溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

連續(xù)子數(shù)組的最大和

發(fā)布時(shí)間：2020-07-16 09:45:20 來(lái)源：網(wǎng)絡(luò) 閱讀：369 作者：栗先生 欄目：編程語(yǔ)言

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


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

    這個(gè)方法，也適合數(shù)組內(nèi)全是負(fù)數(shù)的情況，如果哪位大神發(fā)現(xiàn)了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;

}



向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手