两个连续最大子序和

两个连续最大子序和

给定一个整型数列，你需要找到两个连续子段，保证两个子段不能重复，并且使得这两个字段中的所有整数的和最大

//输入//多少行//数组长度//数组值310 1 -1 2 2 3 -3 4 -4 5 -55-5 9 -5 11 2010-1 -1 -1 -1 -1 -1 -1 -1 -1 -1//输出1340-2

#include#include#includeusing namespace std;#define M 10000int main(){ int N; cin >> N; vectorrecord(M, 0); vectordp(M, 0); vectorRight(M, 0); vectorLeft(M, 0); while (N--) { int i, n = 0; cin >> n; for (i = 1; i <= n; i++) cin >> record[i]; Left[0] = Right[n + 1] = dp[n + 1] = dp[0] = -M; for (i = 1; i <= n; i++)//正向 { dp[i] = max(dp[i - 1] + record[i], record[i]); } for (i = 1; i <= n; i++) { Left[i] = max(Left[i - 1], dp[i]); } for (i = n; i >= 1; i--) { dp[i] = max(record[i], dp[i + 1] + record[i]); } for (i = n; i >= 1; i--)//逆向 { Right[i] = max(Right[i + 1], dp[i]); } int sum = -M;//枚举 for (i = 1; i <= n; i++) { sum = max(Left[i] + Right[i + 1], sum); } cout << sum << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。