本文主要是介绍浙大数据结构:01-复杂度2 Maximum Subsequence Sum,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
数据结构MOOC
PTA习题
01-复杂度2 Maximum Subsequence Sum
#include <iostream>
using namespace std;
const int M = 100005;
int a[M];
int main()
{int k;cin >> k;int f = 1;for (int i = 0; i < k; i++){cin >> a[i];if (a[i] >= 0)//如果出现大于0则进行在线处理f = 0;}if (f){ //全都小于0cout << "0" << ' ' << a[0] << ' ' << a[k - 1];return 0;}int s = 0, ma = -1, l = 0, j = 0, r;for (int i = 0; i < k; i++){s += a[i];if (s > ma){ //更新答案ma = s;r = a[i];l = a[j];}if (s < 0){s = 0;j = i + 1; //因为扔掉了左边,所以答案数组的左指针一定大于i}}cout << ma << ' ' << l << ' ' << r;return 0;
}
这篇关于浙大数据结构:01-复杂度2 Maximum Subsequence Sum的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!