浅谈最大子序和中的dp优化策略

参考资料
本题tyvj题解
《算法艺术与信息学竞赛》

Tyvj P1305 最大子序和

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。
例如

1，-3,5,1，-2,3
当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6

输入格式

第一行两个数n,m
第二行有n个数，要求在n个数找到最大子序和

输出格式

一个数，数出他们的最大子序和

测试样例

输入

6 4 
1 -3 5 1 -2 3

输出

备注

数据范围：
100%满足n,m<=300000

第一步：50分

这是经典问题最大子数组的修改版，乍一看似乎有点无从下手。但是经过分析不难得出一个2D/0D的dp方程。不妨用f(i,j)表示前i个数向前j个的子序和的最大值。注意题目中的要求 不超过M ，所以决策有以下几种：

当j=0时，f(i,j) = 0
如果f(i-1, j-1) > 0，那么f(i, j) = f(i-1, j-1)+a[i]
否则 f(i,j) = 0

在这个思想的指导下，不难写出dp方程:
f(i,j) = max(0, f(i-1, j-1)+a[i])
最后的结果是max{f(i,M) | 1≤i≤n}
显然i，j都是递增的，只要简单地i，j递增dp就可以解决问题了

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n, m;
int a[4001];
int dp[4001][4001];
int main() {
  scanf("%d%d", &n, &m);
  for (int i=1; i<=n; i++)
    scanf("%d", &a[i]);
  memset(dp, 0, sizeof dp);
  for (int i=1; i<=n; i++) {
    for (int j=1; j<=m; j++)
      if (dp[i-1][j-1]+a[i] > 0)
        dp[i][j] = dp[i-1][j-1]+a[i];
  }
  int ans = 0;
  for (int i=1; i<=n; i++)
    ans = max(ans, dp[i][m]);
  cout << ans;
  return 0;
}

这个方法的正确性是显然的，但是空间上显然不够，还有很大优化的空间。

第二步：70分

不难发现每一个f(i,j)都只依赖于f(i-1, j-1)，所以可以省略多余的空间，只剩下两列，一行储存上一次的数据，一行记录这次数据，通过dp[N][2]互相交换使用空间来压缩一维空间复杂度。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n, m;
int a[300005];
int dp[2][300005];
int main() {
  scanf("%d%d", &n, &m);
  for (int i=1; i<=n; i++)
    scanf("%d", &a[i]);
  memset(dp, 0, sizeof dp);
  int ans = 0;
  for (int i=1; i<=n; i++) {
    for (int j=1; j<=m; j++)
      if (dp[0][j-1]+a[i] > 0) {
        dp[1][j] = dp[0][j-1]+a[i];
        ans = max(dp[1][j], ans);
      }
      else
        dp[1][j] = 0;
      // 这里不要忘记
    for (int j=1; j<=m; j++)
      dp[0][j] = dp[1][j];
    // 交换数据空间和运算空间
  }
  cout << ans;
  return 0;
}

虽然滚动数组能把空间复杂度控制在可以接受的范围内，但是他的时间速度O(NM)仍然令人难以接受。我们需要进一步优化或是寻找一种新的方法来解决这个问题。

第三步：AC！

我们来看看前两种方法所用的方程： f(i,j) = max(0, f(i-1, j-1)+a[i])。
其中，状态是二维的，决策是一维的，我们称这个方程是2D/0D的。显然状态是无法优化的，这个方程几乎没有优化余地。我们不妨将j的一维放到决策中。得到新方程：f(i) = max{sum(k..i)|i-k≤M}
区间和用前缀和处理，不难得到方程 f(i) = max{sum[i]-sum[i-k]|k≤M}
提出常数 f(i) = sum[i]-min{sum[k]|i-M≤k≤i-1}
至此，我们成功的把2D/0D方程变成了一个贪心式。显然，后面区间最小值可以用st算法或者线段树解决。复杂度降到了Θ(NlgN)。给出一个用ST算法实现的代码。

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;

#define ll long long
#define maxn 300030
ll dp[maxn][30];
ll n, q;
#define TwoPow(x) ((1)<<(x))

void init() {
  for (ll i = 1; i <= 20; i++)
    for (ll j = 1; j <= n; j++)
      if (j + TwoPow(i) - 1 <= n)
        dp[j][i] = min(dp[j][i - 1], dp[j + TwoPow(i - 1)][i - 1]);
}

ll ask(int i, int j) {
  if (i <= 0)
    i = 0;
  int k = (int)(log(j - i + 1) / log(2));
  return min(dp[i][k], dp[j - TwoPow(k) + 1][k]);
}

int main() {
  memset(dp, 127 / 3, sizeof(dp));
  scanf("%lld%lld", &n, &q);
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &dp[i][0]);
    dp[i][0] += dp[i - 1][0];
  }
  init();
  ll ans = 0;
  for (int i = 1; i <= n; i++)
    ans = max(ans, dp[i][0] - ask(i - q, i - 1));
  cout << ans;
  return 0;
}

总结

这个题目很好的呈现了dp优化过程，最后还是可以用单调队列优化到Θ(N)，不过Θ(NlgN)已经可以AC了。把dp变为贪心，再用其他手段可以大大优化dp的复杂度。

Ps：http://blog.csdn.net/OIljt12138/article/details/51174560
这里介绍用Θ(n)解决此问题的方法。