浙大数据结构：01-复杂度1 最大子列和题目

数据结构MOOC
PTA习题

01-复杂度1 最大子列和题目

使用在线处理处罚，遍历数组，假如当前数组和小于0则扬弃，每次更新最大值。
我们假设终极效果为数组中央的一段，那么左边剩余的部分和右边剩余的部分和肯定小于0，对答案没有贡献。

1. #include <iostream>
2. using namespace std;
4. const int M=100005;
5. int a[M];
6. int main()
7. {
8.     int k;
9.     cin>>k;
10.     for(int i=0;i<k;i++ )cin>>a[i];
12.     int s=0,ma=0;
13.     for(int i=0;i<k;i++)
14.     {
15.         s+=a[i];
16.         ma=max(s,ma);
17.         if(s<0)
18.         {
19.             s=0;
20.         }
21. }
22.     cout<<ma;
23.    
24.         return 0;
25.        
26. }

复制代码