1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
#include<stdio.h> #define N 1000
int MaxSum(int a[],int left,int right){ int sum=0,midSum=0,leftSum=0,rightSum=0; int center,s1,s2,lefts,rights; if(left==right){ sum=a[left]; } else{ center=(left+right)/2; leftSum=MaxSum(a,left,center); rightSum=MaxSum(a,center+1,right); s1=0;lefts=0; for(int i=center;i>=left;i--){ lefts+=a[i]; if(lefts>s1) s1=lefts; } s2=0;rights=0; for(int j=center+1;j<=right;j++){ rights+=a[j]; if(rights>s2)s2=rights; } midSum=s1+s2; if(midSum<leftSum)sum=leftSum; else sum=midSum; if(sum<rightSum)sum=rightSum; } return sum; }
int main(){ int a[N]={0};
for(int i=0;i<(sizeof(a)/4);i++){ scanf("%d",&a[i]); if(a[i]==0)break; } printf("%d",MaxSum(a,0,sizeof(a)/4)); return 0; }
|