codeforce每日一题
题目链接
题目分数:1800
题目描述
输入$n(1≤n≤5000)$ 和长为 $n$ 的数组 $a(-1e9≤a[i]≤1e9)$。
定义 $s(i,i)=0, s(i,j)=a[i]+a[i+1]+…+a[j-1]$。
计算 $s(0,i)-s(i,j)+s(j,k)-s(k,n)$ 的最大值,其中 $0≤i≤j≤k≤n$。
你需要输出最大值对应的 $i,j,k$。
如果有多个满足要求的答案,输出任意一个。
样例
输入样例1
3
-1 2 3
输出样例1
0 1 3
输入样例2
4
0 0 -1 0
输出样例2
0 0 0
输入样例3
1
10000
输出样例3
1 1 1
算法
(枚举) $O(n)$
我们可以将等式化简成为$2*(s[i] - s[j] + s[k]) - s[n]$,s数组表示前缀和。则我们就先预处理一个前缀和,再维护两个前缀最大值,遍历一遍即可找出最大值。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
vector<int> w(n + 1);
rep(i, 1, n) cin>>w[i];
vector<LL> s(n + 1, 0);
vector<PLL> g1(n + 2, {0, 0}), g2(n + 2, {0, 0});
rep(i, 1, n) s[i] += s[i - 1] + w[i];
rep(i, 1, n){
g1[i].fi = max(g1[i-1].fi, s[i]);
if(g1[i].fi==s[i]) g1[i].se = i;
else g1[i].se = g1[i-1].se;
}
g2[n + 1] = {-1e18, 0};
per(i, 1, n)
{
g2[i].fi = max(g2[i+1].fi, s[i]);
if(g2[i].fi==s[i]) g2[i].se = i;
else g2[i].se = g2[i+1].se;
}
LL res = -1e18;
vector<int> ans(3);
rep(i, 0, n){
LL tmp = g1[i].fi - s[i] + g2[i].fi;
if(res<tmp){
res = tmp;
ans[0] = g1[i].se, ans[1] = i, ans[2] = g2[i].se;
}
}
cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<endl;
return 0;
}
Java 代码
// https://www.acwing.com/blog/content/34755/
import java.util.*;
public class Main{
public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f;
public static void solve()
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] w = new int[n + 1];
for(int i=1;i<=n;i++) w[i] = sc.nextInt();
long[] s = new long[n + 1];
long[] g = new long[n + 1];
int[] idx = new int[n + 1];
for(int i=1;i<=n;i++) s[i] = s[i - 1] + w[i];
for(int i=1;i<=n;i++){
g[i] = Math.max(g[i - 1], s[i]);
if(g[i] == s[i]) idx[i] = i;
else idx[i] = idx[i - 1];
}
long res = -1000000000;
int[] ans = new int[3];
long S = s[n];
int idx1 = n;
for(int i=n;i>=0;i--)
{
if(s[i] > S){
S = s[i];
idx1 = i;
}
long tmp = g[i] - s[i] + S;
if(tmp > res)
{
res = tmp;
ans[0] = idx[i];ans[1] = i; ans[2] = idx1;
}
}
System.out.printf("%d %d %d", ans[0], ans[1], ans[2]);
}
public static void main(String[] args)
{
solve();
}
}
Python 代码
# https://www.acwing.com/blog/content/34755/
def solve():
n = int(input())
w = [int(i) for i in input().split()]
w.insert(0, 0)
s = [0] * (n + 1)
for i in range(1, n + 1): s[i] = s[i - 1] + w[i]
g1 = [0] * (n + 1)
idx = [0] * (n + 1)
for i in range(1, n + 1):
g1[i] = max(g1[i - 1], s[i])
if g1[i] == s[i]: idx[i] = i
else: idx[i] = idx[i - 1]
res = -1e18
S, idx1 = s[n], n
for i in range(n, -1, -1):
if S < s[i]:
S = s[i]
idx1 = i
tmp = g1[i] - s[i] + S
if tmp > res:
res = tmp
# print(res)
ans = [idx[i], i, idx1]
print(ans[0], ans[1], ans[2])
def main():
solve()
if __name__ == '__main__':
main()