基本思想关键点详见 "数据结构典型问题"
- #include<iostream>
- #include<stdlib.h>
- #include<stdio.h>
- #include<vector>
- #include<string>
- #include<math.h>
- #include<algorithm>
- #include<cstring>
- #include<map>
- #include<queue>
- #include<set>
- #include<stack>
- using namespace std;
- int n;
- vector<int>num;
- vector<int>dp;
- vector<int>root;
- int main() {
- cin>> n;
- int st, ed;
- bool flag = true;
- //num.resize(n);
- dp.resize(n);
- root.resize(n);
- int a;
- for (int i = 0; i <n; i++) {
- cin>> a;
- num.push_back(a);
- if (a>= 0)
- flag = false;
- }
- if (flag) {
- printf("%d %d %d\n", 0, num[0], num[num.size() - 1]);
- return 0;
- }
- dp[0] = num[0];
- for (int i = 1; i <n; i++) {
- if (dp[i - 1] + num[i] <= num[i]) {
- // 如果加上 num[i] 反而变小了;
- dp[i] = num[i];
- root[i] = i;// 从新开始开路径
- }
- else {
- // 如果加上变大了
- dp[i] = num[i] + dp[i - 1];
- root[i] = root[i - 1];
- }
- }
- int k = 0;
- for (int i = 1; i < n; i++) {
- if (dp[i]> dp[k])
- k = i;
- }
- printf("%d %d %d\n", dp[k], num[root[k]], num[k]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3434063.html