2 条题解
-
1
题解
题意
给定长度为 的整数序列,必须恰好选择一个区间 进行反转。反转后求整个序列的最大子段和,子段非空。
思路
记:
fl[i]:原序列前缀 中的最大子段和;fr[i]:原序列后缀 中的最大子段和。
这两个数组可以通过两次 Kadane 算法求出。
反转一个区间后,最大子段和可能有两种情况:
- 不需要利用反转,答案就是原序列的最大子段和,即
fl[n]; - 最大子段由原序列中左右两个不重叠的子段拼接而成。
对于第二种情况,可以枚举分界点 :
- 左半部分取前缀 中的最大子段和
fl[i]; - 右半部分取后缀 中的最大子段和
fr[j]。
这两个子段在原序列中不重叠。通过反转左子段起点到右子段起点前一个位置,可以把左子段翻到右子段前面,使它们相邻,从而形成一个连续子段,其和正好为:
因此答案为:
$$\max\left(fl[n],\ \max_{1\le i<j\le n}(fl[i]+fr[j])\right)$$由于题目要求恰好反转一次,如果最优答案就是原序列最大子段和,可以反转一个长度为 的区间,等价于不改变序列,因此不影响答案。
正确性说明
反转操作只改变元素顺序,不改变元素本身。反转后任意一个连续子段映射回原序列,至多由两段不重叠的区间组成,因此其和不会超过“某个前缀最大子段和 + 某个后缀最大子段和”。
另一方面,对于任意 ,取
fl[i]对应的左子段和fr[j]对应的右子段,它们不重叠。反转左子段起点到右子段起点前一个位置后,左子段会被移动到右子段左侧并与其相邻,形成一个和等于fl[i]+fr[j]的连续子段。所以枚举所有 的
fl[i]+fr[j]即可覆盖所有可能由反转产生的最优情况。复杂度
- 时间复杂度:
- 空间复杂度:
, 可以通过。
参考代码
#include<bits/stdc++.h> #define int long long using namespace std; int n; int a[5005]; int fl[5005],fr[5005]; signed main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int res=0,maxx=INT_MIN; for(int i=1;i<=n;i++){ res=max(a[i],res+a[i]); maxx=max(maxx,res); fl[i]=maxx; } res=0,maxx=INT_MIN; for(int i=n;i>=1;i--){ res=max(a[i],res+a[i]); maxx=max(maxx,res); fr[i]=maxx; } int ans=fl[n]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ans=max(ans,fl[i]+fr[j]); cout<<ans; return 0; } -
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; }
- 1
信息
- ID
- 5
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 显示难度普及
- 标签
- 递交数
- 4
- 已通过
- 3
- 上传者