from:https://www.shiyanlou.com/courses/running/102
输入一组整数,求出这组数字子序列和中的最大值,只要求出最大子序列的和,不必求出最大值对应的那个序列。
序列:-2 11 -4 13 -5 2 -5 -3 12 -9 最大子序列和为21
序列:0 -3 6 8 -20 21 8 -9 10 -1 3 6 5 最大子序列和为43
代码如下:
1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 int n,a[20]; 6 cout<<"input n and array"<<endl; 7 cin>>n; 8 for(int i=0;i<n;i++) 9 { 10 cin>>a[i]; 11 } 12 int wai_sum=0; 13 int li_sum=0; 14 for(int i=0;i<n;i++) 15 { 16 li_sum=0; 17 int temp=0; 18 int flag=-1; 19 for(int j=i;j<n;j++) 20 { 21 temp = temp + a[j]; 22 if(a[j]<=0) 23 { 24 continue; 25 } 26 if(li_sum<temp) 27 { 28 li_sum = temp; 29 } 30 } 31 if(wai_sum<li_sum) 32 wai_sum = li_sum; 33 } 34 cout<<wai_sum<<endl; 35 return 0; 36 }
另外的一种时间复杂度更低的方法:
1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 int a[10] = {-2,11,-4,13,-5,2,-5,-3,12,-9}; 6 int b,sum; 7 b=a[0]; 8 sum = a[0]; 9 for(int i=0;i<10;i++) 10 { 11 if(b>0) 12 { 13 b+=a[i]; 14 } 15 else 16 { 17 b = a[i]; 18 } 19 if(b>sum) 20 sum = b; 21 } 22 cout<<sum<<endl; 23 return 0; 24 }