子数组的最大和 - webdancer's Blog

子数组的最大和

webdancer posted @ 2011年3月30日 03:57 in 算法 with tags 算法 , 1486 阅读

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

分析：由于数组里有正数也有负数，所以不存在全为负数情况；所以，依据+正数变大，+负数变小的原理。代码如下：

#include<stdio.h>

int maxsubarr(int a[],int n){
    int i,cur,max;
    
    cur=0;
    max=0;
    for(i=0;i<n;i++){
        cur+=a[i];
        if(cur>max)
            max=cur;
        if(cur<0)
            cur=0;
    }
    return max;
}

int main(){
    int a[]={-1,0,-2,1,2,3,4,-2,3,4,-1,2,4};
    int n=sizeof a/sizeof a[0];
    printf("the maxsum of the sub:%d\n",maxsubarr(a,n));

    return 0;
}