HDU 1024 Max Sum Plus Plus

HDU 1024

dp[i][j]:前j个数的最大i子段和,且最后一段以第j个数结尾.
状态转移方程: dp[i][j]=max(dp[i][j-1]+a[j] , max{ dp[i-1][k] } + a[j] ) 0<k<j
max{dp[i-1][k]}在上一轮计算的时候可以确定, 于是提前记录下来,如此时间复杂度为O(N^2).
然后可以用滚动数组优化,防止爆数组.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int a[1000005];
ll dp[1000005];
ll max_last[1000005];

int main() {
  int n, m;
  while (~scanf("%d%d",&m,&n)) {
    memset(dp,0,sizeof(dp));
    memset(max_last,0,sizeof(max_last));
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
    }
    ll ans = 0,maxx;
    for (int i = 1; i <= m; ++i) {
      maxx=-maxn;
      for (int j = i; j <= n; ++j) {
        dp[j] = max(max_last[j-1], dp[j - 1]) + a[j];
        max_last[j-1]=maxx;
        maxx=max(dp[j],maxx);
      }
    }
   printf("%lld\n",maxx);
  }
  return 0;
}