首先,本题无论什么做法都是计算区间和,所以必须要建立前缀和数组,来通过O(1)计算任意区间和
1.暴力做法
使用三重循环,依次遍历三个变量$x, y, z$,时间复杂度$O(n^3)$,$5000^3=1.25* 10^{11}$,一定会超时。结果用例过了8/15
2. 遍历优化
通过图示,可以看到通过固定y,将此问题拆分成两个独立的小问题,可以分别解决两个相互不影响的两个子问题,通过该方法,将一个$n^3$的算法优化为$n * (2 * n) = 2n^2$。
能进行此优化的重要前提是通过固定y,枚举x的结果不影响z,所以可以分开进行枚举。
这是一个重要的思想,拆分为互不影响的子问题来降低时间复杂度,值得学习和进一步研究。
感谢小林同学的思路
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;
using ll = long long;
const int N = 5e3 + 10;
int n;
int a[N];
ll s[N];
ll get(int l, int r)
{
if(l > r)
return 0;
return s[r] - s[l - 1];
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ )
cin >> a[i];
for(int i = 1; i <= n; i ++ )
s[i] = s[i - 1] + a[i];
int x, y, z;
ll sum_max = LLONG_MIN;
for(int j = 1; j <= n + 1; j ++ )
{
int _x = j, _y = j, _z = n + 1;
ll _sum_min_l = 0;
for(int i = 1; i <= j; i ++ )
{
if(get(i, j - 1) < _sum_min_l){
_sum_min_l = get(i, j - 1);
_x = i;
}
}
ll _sum_min_r = 0;
for(int k = j; k <= n + 1; k ++ )
{
if(get(k, n) < _sum_min_r){
_sum_min_r = get(k, n);
_z = k;
}
}
ll _sum_max = get(1, _x - 1) - get(_x, _y - 1) + get(_y, _z - 1) - get(_z, n);
if(_sum_max > sum_max){
sum_max = _sum_max;
x = _x, y = _y, z = _z;
}
}
cout << x - 1 << " " << y - 1 << " " << z - 1 << endl;
return 0;
}
3. 状态优化遍历
竞赛时使用的奇技淫巧将时间复杂度优化到$O(n^2)$
前两重循环遍历x和y
其中z的位置可以通过f数组得出
f[y] = z是什么?f[y]是从下标y开始,使得sum=(a[z] ~ a[n])小于0且和最小的小标z
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;
using ll = long long;
const int N = 5e3 + 10;
int n;
int a[N];
ll sf[N], sb[N];
int f[N]; // f[i] = x, from i begin, the sb[x] is the min;
ll get(int l, int r)
{
if(l > r)
return 0;
return sf[r] - sf[l - 1];
}
int main()
{
int x, y, z;
cin >> n;
for(int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++ )
sf[i] = sf[i - 1] + a[i];
for(int i = n; i >= 1; i -- )
sb[i] = a[i] + sb[i + 1];
ll sb_min = 0;
int sb_min_index = n + 1;
for(int i = n; i >= 1; i -- )
{
if(sb[i] < sb_min){
sb_min_index = i;
sb_min = sb[i];
}
f[i] = sb_min_index;
}
ll sum_max = LLONG_MIN;
for(int len = 0; len <= n; len ++ )
{
for(int i = 1; i <= n - len; i ++ )
{
ll sum = get(1, i - 1) - get(i, i + len - 1) + get(i + len, f[i + len] - 1) - get(f[i + len] ,n);
if(sum > sum_max){
sum_max = sum;
x = i, y = i + len, z = f[i + len];
}
}
}
cout << x - 1 << " " << y - 1 << " " << z - 1 << endl;
return 0;
}