最大子列问题(在线算法)

给出一列数据,查找并输出其最大子列。

#include<iostream>
using namespace std;
//在线:没输入一个数据就进行及时处理,在任何地方终止输入,都能给出正确当前解
//寻找最大子列
int MaxSubseqSum(int A[], int N) {
int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for (i = 0; i < N; i++) {
ThisSum += A[i];//向右累加
if (ThisSum > MaxSum)
MaxSum = ThisSum;//发现更大和则更新当前结果
else if (ThisSum < 0)//当前子列和为负
ThisSum = 0;//则不能使后面的部分和增大,抛弃之
}
return MaxSum;
}
int main()
{
int b[1000000] = {};
int num;
cin >> num;
for (int i = 0; i < num; i++)
{
cin >> b[i];
}
int xx = MaxSubseqSum(b, num);
cout << xx;
return 0;
}

上一篇:P3806 【模板】点分治1题解


下一篇:leetcode(24)-最大子序列和