将这个数组首尾相接连成一个环状,它的一个子序列是指这个数组连续的一段,比如a2,a3…ak,或者an,a1…ai。请从这个环上选取两个不重叠的非空子序列,使这两个子序列中的所有数字之和最大。
在三个样例中分别选取的子序列是:
样例一:
{a1} {a3}
样例二: {a1} {a3}
样例三: {a5,a1} {a3}
接下来每个测试数据包含两行,第一行是一个正整数n(2<=n<=50000),
第二行是用空格隔开的数组A的n个数,依次为a1,a2,…an (|ai|<=10000)。
3 3 1 -1 0 4 1 -1 1 -1 5 1 -1 1 -1 1
1 2 3
算法:分别求两段最大和以及两段最小和即可。
论坛上看到的,我加了注释
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
using namespace std;
int data[50001];
int ff[50001], bb[50001];
int n;
int solve()
{
int s = 0;
//ff[i]表示范围0->i的数据构成的最大子段值,可以不取,值永远非负
for (int i = 0; i < n; ++i) {
if (i) ff[i] = ff[i - 1];
else ff[i] = 0;
if (s < 0) s = 0; //s表示从0->i,以i结尾的最大子段值
s += data[i];
ff[i] = max(ff[i], s); //取以i结尾的最大字段值与历史上最大的最大子段值的最大值
}
s = 0;
//这个步骤和上面类似,只不过是从右往左处理,bb[i]表示从n - 1 ~ i构成的最大字段值
for (int i = n - 1; i >= 0; --i) {
if (i < n - 1) bb[i] = bb[i + 1];
else bb[i] = 0;
if (s < 0) s = 0;
s += data[i];
bb[i] = max(bb[i], s);
}
//遍历断开的位置,取最大值
int ans = 0;
for (int i = 0; i < n - 1; ++i)
ans = max(ans, ff[i] + bb[i + 1]);
return ans;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int sum = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
scanf("%d", &data[i]);
sum += data[i];
if (data[i] > 0) cnt++;
}
//由于solve不能处理正数元素小于等于2的情况,因此需要单独处理
if (cnt <= 2) {
sort(data, data + n, greater <int>());
printf("%d/n", data[0] + data[1]);
continue;
}
int s1 = solve(); //正的最大子段
for (int i = 0; i < n; ++i) //求反数的最大子段,相当与求最小子段
data[i] = -data[i];
int s2 = sum + solve(); //去除最小子段
printf("%d/n", max(s1, s2));
}
return 0;
}