枚举过去了QAQ
(暴力枚举) $O(n^2)$
从数据范围可以看出来大致可以 $O(n^2)$ , 朴素的想法就是直接三层遍历,但是肯定会超时
所以考虑一下怎么枚举,三个变量xyz由于有大小关系所以可以先固定y,再在y的循环中确定 x 和 z即可
计算
求和过程需要按照题目的定义 s(l,r) 不能包含 a[r]
计算过程中把式子拆成两个新式的加法即可
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 5010;
int n;
int a[N];
LL s[N];
inline LL getSum(int l, int r)
{
return s[r-1] - s[l-1];
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d", a+i), s[i] = s[i-1] + a[i];
int x = 1, y = 1, z = 1;
LL maxSum = -0x3f3f3f3ff3f3f3f;
for(int yy = 1; yy <= n+1; yy ++)
{
LL res1 = -0x1f3f3f3ff3f3f3f, res2 = -0x1f3f3f3ff3f3f3f;
int tx = 1, tz = 1;
for(int xx = 1; xx <= yy; xx ++)
{
LL tt = getSum(1, xx) - getSum(xx, yy);
if(res1 < tt)
{
res1 = tt;
tx = xx;
}
}
for(int zz = yy; zz <= n+1; zz ++)
{
LL tt = getSum(yy, zz) - getSum(zz, n+1);
if(res2 < tt)
{
res2 = tt;
tz = zz;
}
}
if(maxSum < res1 + res2)
{
maxSum = res1 + res2;
x = tx, y = yy, z = tz;
}
}
printf("%d %d %d\n", x-1, y-1, z-1);
//cout << maxSum << endl;
return 0;
}
$\texttt{orz}$
orz