OnlineCode

[xiyoulaoyuanjia]

一个整型数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组的和的最大值，要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，那么最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18， 请完成函数int MaxSum(int* a,int n)。

#include <stdio.h>
#include <string.h>

int MaxSum(int* a,int n)
{
     int i=0;
    int initSum=a[0];
    int aSum=0;
    for(i=0;i<n;i++){
        aSum=aSum+a[i];
        if(aSum<0 && i != n-1){
            aSum=a[i+1];
            i++;
        }
        if(aSum>initSum){
            initSum=aSum;
        }
    }
  return initSum;
}
//start 提示：本行为自动阅卷起始唯一标识，请勿删除或增加。
//完成下面main函数，自行测试下
int main()
{   
    //wirte your code here;
int a[]={1,-2,3,10,-4,7,2,-5};
    printf("%d",sumMax(a,8));
    return 0;  
} 
//end   提示：本行为自动阅卷结束唯一标识，请勿删除或增加。