Java教程

最大子列问题（在线算法）

本文主要是介绍最大子列问题（在线算法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

#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;
}

这篇关于最大子列问题（在线算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航