53. Maximum Subarray

創(chuàng)新互聯(lián)建站主要從事成都網(wǎng)站制作、做網(wǎng)站、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)無為,10年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

題意：

根據(jù)給定的數(shù)組，查找和最大的字串。

使用 "Kadane算法"查找最大和字串。

解題：

1）定義變量Max來保存最大和。定義sum來保存中間值的和。

2）數(shù)組連續(xù)幾個(gè)值的和如果為負(fù)數(shù)，也就意味著再往負(fù)數(shù)上加正數(shù)就沒有意義了，加上的和肯定不會大于加上數(shù)的值。此時(shí)重新開始計(jì)算聯(lián)系元素和即可。

3）如果數(shù)組為全負(fù)元素，那么取出最大值即可。

if ( sum <= 0 ) 
{   
    sum = 0;
}
作用保證重新計(jì)數(shù)時(shí)，是從零開始的。

if ( sum <= 0 ) 
{   
    sum = *( nums + cnt );
}
沒有置零而是置為當(dāng)前值，是為了防止全負(fù)數(shù)組時(shí)，能把最大的值存入Max變量中。

Max起始置為INT_MIN保證了int型的任何負(fù)數(shù)都可存入。

int maxSubArray(int* nums, int numsSize) 
{
    int cnt = 0;
    int max = INT_MIN;
    int sum = 0;
    for ( cnt = 0; cnt < numsSize; cnt++ )
    {   
        if ( sum <= 0 ) 
        {   
            sum = 0;
        }
        
        sum = sum + *( nums + cnt );
        if ( sum <= 0 ) 
        {   
            sum = *( nums + cnt );
        }
        
        if ( sum > max )
        {   
            max = sum;
        }   
    }
     
    return max;
}

新聞標(biāo)題：53.MaximumSubarray
分享地址：http://chinadenli.net/article22/gjcgjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、移動網(wǎng)站建設(shè)、外貿(mào)建站、做網(wǎng)站、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)