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; }
信息
- ID
- 5
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 显示难度普及
- 标签
- 递交数
- 4
- 已通过
- 3
- 上传者