跟着姥姥学数据结构(1) -- 最大子列和

本文主要是介绍跟着姥姥学数据结构(1) -- 最大子列和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

    大学毕业已经两年了，两年的工作中发现自己曾经很差的计算机基础部分还是没有得到锻炼，就在中国大学MOOC上面参加了数据结构的课程。在博客中会把课后作业中的一些题目写出来。

    今天要说的题目是求一个数列的最大子列和，有一个N个整数的序列{A1,A2,A3,A4...AN}，求函数f(x,y)=max{0, Ai+Ai+1+...Aj (1<=i<j<=N)}的最大值.

这题使用在线处理的算法，复杂度最低，为o(n);

代码如下：

#include <iostream>using namespace std;int a[100010];int main()
{int N;while (cin >> N){int thisSum = 0, maxSum = 0;for (int i = 0; i < N; i++){cin >> a[i];thisSum += a[i];if (thisSum > maxSum)maxSum = thisSum;else if (thisSum < 0)thisSum = 0;}cout << maxSum << endl;}return 0;
}

这篇关于跟着姥姥学数据结构(1) -- 最大子列和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---