最大子段和
1 /*
2 b[]的递归式为
3 b[j]={ b[j-1]+a[j] , b[j-1]>=0
4 a[j] , b[j-1]<0 }
5 */
6 #include <iostream>
7 using namespace std;
8
9 int MaxSum(int n, int *a)
10 {
11 int sum=0;
12 int b=0;
13 for (int i=0;i<n;i++)
14 {
15 if (b>0) b+=a[i]; else b=a[i];
16 if (b>sum) sum=b;
17 }
18 return sum;
19 }
20
21 int main()
22 {
23 int a[]={-1,3,-4,5,-3,6,7,-7};
24 int sum = MaxSum(8,a);
25 cout<<sum<<endl;
26 return 0;
27 }