(双子序列最大和)给定一个长度为 n(3≤n≤1000) 的整数序列,要求从中选出两个连续子序列,使得这两个连续子序列的序列和之和最大,最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求:每个连续子序列长度至少为 1,且两个连续子序列之间至少间隔 1 个数。(第五空 4 分,其余 2.5 分)
#include <iostream> using namespace std; const int MAXN = 1000; int n, i, ans, sum; int x[MAXN]; int lmax[MAXN]; // lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中,最大的序列和 int rmax[MAXN]; // rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中,最大的序列和 int main() { cin >> n; for (i = 0; i < n; i++) cin >> x[i]; lmax[0] = x[0]; for (i = 1; i < n; i++) if (lmax[i - 1] <= 0) lmax[i] = x[i]; else lmax[i] = lmax[i - 1] + x[i]; for (i = 1; i < n; i++) if (lmax[i] < lmax[i - 1]) lmax[i] = lmax[i - 1]; (1) ; for (i = n - 2; i >= 0; i--) if (rmax[i + 1] <= 0) (2) ; else (3) ; for (i = n - 2; i >= 0; i--) if (rmax[i] < rmax[i + 1]) (4) ; ans = x[0] + x[2]; for (i = 1; i < n - 1; i++) { sum = (5) ; if (sum > ans) ans = sum; } cout << ans << endl; return 0; }