2 条题解
-
1
显然可以O(n)做
考虑反转有效果当且仅当反转后的最大子段和对应的子段与反转区间有交,且不重合,
问题就变成了从原数组中选两个不交的最大子段,
前缀dp一遍,后缀dp一遍,枚举中间分割线求一下对于每一条分割线,左右的最大子段和之和,最大值,即为答案
代码:#include <bits/stdc++.h> using namespace std; const int maxn=5002; #define int long long int n,a[maxn]; int dp[maxn],dp2[maxn]; signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) dp[i]=max(a[i],dp[i-1]+a[i]); for(int i=2;i<=n;i++) dp[i]=max(dp[i],dp[i-1]); for(int i=n;i>=1;i--) dp2[i]=max(a[i],a[i]+dp2[i+1]); for(int i=n-1;i>=1;i--) dp2[i]=max(dp2[i],dp2[i+1]); int ans=-0x3f3f3f3f3f3f3f3f; for(int i=0;i<=n;i++) ans=max(ans,dp[i]+dp2[i+1]); cout<<ans<<endl; return 0; }
信息
- ID
- 5
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 显示难度普及
- 标签
- 递交数
- 4
- 已通过
- 3
- 上传者