Abstract
本文主要介绍各种序列子段和问题。
P1 最大子段和
Introduction
首先来看一道经典例题,求一段序列的最大子段和
Idea
考虑动态规划,令 dp[i] 表示在取第 i 个数的情况下,前 i 个数所能得到的最大子段和,那么显然有 dp[i] = max( dp[i-1] + a[i] , a[i]),其中 a[i] 表示序列的第 i 个数。
Code
#include <bits/stdc++.h>
using namespace std;
int dp[300000];
int ans = -INT_MAX;
int main()
{
int n;
cin >> n;
memset(dp, -0x3f3f3f, sizeof dp);
for (int i = 1; i < n + 1; i++)
{
int m;
cin >> m;
dp[i] = max(dp[i - 1] + m, m);
ans = max(ans, dp[i]); // 注意答案每次都要更新
}
cout << ans;
return 0;
}
P2 双子序列最大和
Introduction
再看一道升级版的,这次我们需要找出两个不重叠的子段,使他们的各自的子段和之和达到最大值。
Idea
一个显然的想法是,我们可以依次枚举序列中的每一项,然后分别找出这一项右侧和左侧的最大子段和,然后将他们相加即可。这样一来,问题就变得和 P1 极其相似了。
我们不妨以 l[i] 表示第 i 项左边的数可以得到的最大子段和,r[i] 表示第 i 项右边的数可以得到的最大子段和,答案就是 max( l[i] + r[i] ), i = 2,3...n-1。
下面考虑如何计算 l[i] 和 r[i] , 和 P1 类似的,我们可以写出以下转移方程 l[i] = max( l[i-1] + a[i-1], a[i-1]), r[i] = max ( r[i+1] + a[i+1] , a[i+1]),这样一来,我们就成功得到了选取第 i-1/i+1 个数时,第 i 个数左侧/右侧的数所能取得的最大子段和,然后,我们对 l,r 数组做以下处理:l[i] = max( l[i] , l[i-1] ),r[i] = max( r[i] , r[i+1] ),这样一来,就将 l,r 数组转变为我们需要的东西了。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1100000;
int l[maxn];
int r[maxn];
int a[maxn];
signed main()
{
int n;
scanf("%lld", &n);
memset(l, -0x3f3f3f3f, sizeof l);
memset(r, -0x3f3f3f3f, sizeof r);
l[1] = l[0] = 0;
r[n] = r[n + 1] = 0;
scanf("%lld ", &a[1]);
for (int i = 2; i < n + 1; i++)
{
scanf("%lld", &a[i]);
l[i] = max(l[i - 1] + a[i - 1], a[i - 1]);
}
for (int i = n - 1; i > 0; i--)
{
r[i] = max(r[i + 1] + a[i + 1], a[i + 1]);
}
for (int i = n - 1; i > 0; i--)
{
r[i - 1] = max(r[i - 1], r[i]);
}
for (int i = 2; i < n + 1; i++)
{
l[i + 1] = max(l[i + 1], l[i]);
}
int ans = -0x3f3f3f3f;
for (int i = 2; i < n; i++)
{
ans = max(l[i] + r[i], ans);
}
cout << ans;
return 0;
}
P3 环状最大两段子段和
Introduction
这一题是 P2 的进阶版本,怎样在环形序列中找到子段和最大的两端不重叠序列呢?
Idea
实际上,可能的情况只有两种(0表示不选,@表示选):
- 000@@@000@@@000
- @@@000@@@000@@@
第一种情况和 P2 是完全一致的,第二种情况看似有些变化,但仔细一想,选出和最大的 @ 和选出和最小的 0 好像是等价的啊!那么我们只需要把序列中的数全部都取相反数,然后再重复 P2 的操作就可以了,此题得解。
Code
#include <bits/stdc++.h>
using namespace std;
int n;
int a[300000];
int dp_l[300000];
int dp_r[300000];
int sum;
bool ok;
int main()
{
scanf("%d", &n);
for (int i = 1; i < n + 1; i++)
{
scanf("%d", a + i);
if (a[i] > 0)
{
ok = 1;
}
sum += a[i];
}
// 如果全是负数的话,我们只需要把最大的两个负数之和输出就可以了
// 我不知道为啥程序会在这地方出问题所以加了特判qwq
if (!ok)
{
sort(a + 1, a + 1 + n);
cout << a[n] + a[n - 1] << endl;
return 0;
}
// 阶段一
for (int i = 1; i <= n; i++)
{
dp_l[i] = max(dp_l[i - 1] + a[i], a[i]);
}
for (int j = n; j > 0; j--)
{
dp_r[j] = max(dp_r[j + 1] + a[j], a[j]);
}
// 阶段二
for (int i = 1; i <= n; i++)
{
dp_l[i] = max(dp_l[i], dp_l[i - 1]);
}
for (int i = 1; i <= n; i++)
{
dp_r[i] = max(dp_r[i], dp_r[i + 1]);
}
// 更新答案
int ans1 = -INT_MAX;
for (int i = 2; i <= n; i++)
{
ans1 = max(ans1, dp_l[i - 1] + dp_r[i]);
}
// 全部取反
for (int i = 1; i <= n; i++)
{
a[i] *= -1;
}
// 阶段一
for (int i = 1; i <= n; i++)
{
dp_l[i] = max(dp_l[i - 1] + a[i], a[i]);
}
for (int j = n; j > 0; j--)
{
dp_r[j] = max(dp_r[j + 1] + a[j], a[j]);
}
// 阶段二
for (int i = 1; i <= n; i++)
{
dp_l[i] = max(dp_l[i], dp_l[i - 1]);
}
for (int i = 1; i <= n; i++)
{
dp_r[i] = max(dp_r[i], dp_r[i + 1]);
}
int ans2 = -INT_MAX;
for (int i = 2; i <= n; i++)
{
ans2 = max(ans2, dp_l[i - 1] + dp_r[i]);
}
// 把 ans2 变换为我们需要的东西
ans2 *= -1;
ans2 = sum - ans2;
// 输出 ans1,ans2 中较大的
cout << max(ans1, ans2);
return 0;
}
标签:子段,int,max,问题,ans,序列,dp From: https://www.cnblogs.com/carboxylBase/p/18335654