最大M子段和

最大M划分子段和

最大子段和的变种

N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，
并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。

首先构造递推式$dp[i][j]$代表i个数的j划分并且以a[i]结尾。
则可知：
$
dp[i][j]=max{dp[i-1][j],max{dp[k][j-1]}}+a[i] (j-1<=k<i) $
第一项$dp[i-1][j]+a[i]$代表将$a[i]$和前面的元素共同划为第J个划分
第二项$dp[k][j-1]+a[i]$代表把$a[i]$单独划为一项。
由以上递推式可得:

#include <cstdio>
using namespace std;
const int maxn = 5000;
int a[maxn];
const int inf = -(1 << 20);
int dp[maxn][maxn]; 
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  long long sumP = 0;
  int p = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (a[i] > 0) {
      ++p;
      sumP += a[i];
    }
  }
  if (m >= p) {
    printf("%lld\n", sumP);
  } else {
    for (int j = 1; j <= m; j++) {
      for (int i = j; i <= n; i++) {
        dp[i][j] = dp[i - 1][j] + a[i];
        for (int k = j - 1; k < i; k++) {
          if (dp[i][j] < dp[k][j - 1] + a[i])
            dp[i][j] = dp[k][j - 1] + a[i];
        }
      }
    }
    printf("%d\n", dp[n][m]);
  }
}

然而时间复杂度不慎理想$O(mnn)$肯定是不行的。
仔细观察第二项时间主要耗费在寻找$max{dp[k][j-1]}$上怎么优化呢，dp!!
我们再用一个数组$f[i][j]$代表$i$个数$j$划分的最优方案。
可得以下递推式：
$dp[i][j]=max {dp[i-1][j],f[i-1][j-1]}+a[i]$
$f[i][j]=max{dp[i][j],f[i-1][j]}
$
根据以上递推式可得：

#include <algorithm>
#include <cstdio>

using namespace std;
const int maxn = 5000;
int a[maxn];
const int inf = -(1 << 20);
int dp[maxn][maxn];
int f[maxn][maxn];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  long long sumP = 0;
  int p = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (a[i] > 0) {
      ++p;
      sumP += a[i];
    }
  }
  if (m >= p) {
    printf("%lld\n", sumP);
  } else {
    for (int j = 1; j <= m; j++) {
      for (int i = j; i <= n; ++i) {
        dp[i][j] = max(dp[i - 1][j], f[i - 1][j-1]) + a[i];
        f[i][j] = max(f[i - 1][j], dp[i][j]);
      }
    }
    printf("%d\n", f[n][m]);
  }
}

分析时间复杂度可知变为$O(mn)$可以接受，然而空间复杂度变为$2O(m*n)$,变为原来的二倍。仔细观察发现递推式只与相邻的两项有关，可以利用滚动数组来优化。
将原来的数组第二维优化为2。

#include <algorithm>
#include <cstdio>

using namespace std;
const int maxn = 5000+2;
int a[maxn];
const int inf = -(1 << 20);
long long dp[maxn][2];
long long  f[maxn][2];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  long long sumP = 0;
  int p = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (a[i] > 0) {
      ++p;
      sumP += a[i];
    }
  }
  if (m >= p) {
    printf("%lld\n", sumP);
  } else {
    int t = 0, g = 0;
    for (int j = 1; j <= m; j++) {
      t = (j & 1);
      g = 1 - t;
      dp[j - 1][t] = inf;
      for (int i = j; i <= n; ++i) {
        dp[i][t] = max(dp[i - 1][t], f[i - 1][g]) + a[i];
        f[i][t] = max(f[i - 1][t], dp[i][t]);
      }
    }
    printf("%lld\n", f[n][t]);
  }
}

至此，最大M划分子段和成功解决。