浙大数据结构:01-复杂度1 最大子列和问题
数据结构MOOC
PTA习题
01-复杂度1 最大子列和问题
使用在线处理,遍历数组,如果当前数组和小于0则抛弃,每次更新最大值。
我们假设最终结果为数组中间的一段,那么左边剩余的部分和右边剩余的部分和一定小于0,对答案没有贡献。
#include <iostream>
using namespace std;const int M=100005;
int a[M];
int main()
{int k;cin>>k;for(int i=0;i<k;i++ )cin>>a[i];int s=0,ma=0;for(int i=0;i<k;i++){s+=a[i];ma=max(s,ma);if(s<0){s=0;}
}cout<<ma;return 0;}