算法——求數組中最大子數組和

題目

有一輸入數組，數組裡面的數字都是整數，可能為正，可能為負，也可能是0，要求該輸入數組中最大子數組的和。

題目分析
面對這樣的一個問題，首先需要仔細分析問題的條件與問題所求。這個問題提供了一個輸入數組，裡面會有若干個元素，每個元素可以為正數，可以為負數，也可以為0。而題目要求輸出該數組中最大子數組的和，注意是要求連續相鄰的若干元素組成的子數組，並且保證該子數組的和最大。

這個問題具體最優子結構，無後效性等動態規劃的特點，因此可以用動態規劃來解決。

設原輸入數組為data[]，利用另一個數組dp[i]來表示以data[i]結尾的子數組的最大和：

dp[i]=max(sum(data[start....end]))   0<=start<=end<=i

因此最大的子數組就是dp數組中的最大值。

在實際的代碼實現中可以簡化dp數組，用一個變量替代他，並且實時的更新最大和，以及子數組的起始位置和結束位置。

代碼部分
下面是實現該題目的部分代碼：

[cpp] 
#define LENGTH 10 
 
int max_subset(int *data,int len,int *s,int *l) 
{ 
    int max=0; 
    int i,j; 
    int sum=0; 
    int start,end; 
 
    for(i=0;i<len;i++) 
    { 
        if(sum<=0) 
        { 
            sum=data[i]; 
            start=end=i; 
        } 
        else 
        { 
            sum=sum+data[i]; 
            end=i; 
        } 
        if(sum>max) 
        { 
            max=sum; 
            *s=start; 
            *l=end; 
        } 
             
    } 
 
    if(max==0) 
    { 
        max=data[0]; 
        *s=*l=0; 
        for(i=1;i<len;i++) 
        { 
            if(data[i]>max) 
            { 
                max=data[i]; 
                *s=*l=i; 
            } 
        } 
    } 
    return max; 
} 
int main() 
{ 
 
    int data[LENGTH]={-1,-2,3,10,-4,7,-2,5,-9,-1}; 
    int result=0; 
    int s,l; 
    result=max_subset(data,LENGTH,&s,&l); 
    printf(" max sub set is %d  from %d to %d \n",result,s,l); 
 
    return 0; 
} 

小結
這是一道經典的題目，被很多公司筆試面試所采用，值得仔細研究。