HDU 1024 Max Sum Plus Plus【DP,最大mサブセグメント和】

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=1024
タイトル:
与えられたシーケンス、与えられたm、mサブセグメントの最大和を求める.
分析:
dp[i][j]をj番目の要素で終わるiサブセグメントの和とする.各要素に対して前の要素と一緒に1つのサブセグメントを構成することと,1つのサブセグメントを単独で開くことの2つの可能性について,状態遷移方程式

dp[i][j] = max(dp[i][j - 1], dp[i - 1][k]) + a[j] (k >= i - 1 && k <= j - 1)

時間複雑度O(m∗n 2),nは1 e 6に達し,必ずタイムアウトした.次に、スクロール配列を用いて空間と時間の最適化を行うことができる.このdp[i−1][k]は、前のj要素の中性子セグメント数がi−1の最大値である配列を直接開き、ansで現在の数のサブセグメントの最大値を記録し、サブセグメント数が増加する過程で更新される.時間複雑度O(n∗m).ansも配列dpもtもlong longすべきだと思いますが、intもAもできることに気づきました...
コード:

#include<cstdio>
#include<cstring>
#include<iostream>>
using namespace std;
#define sa(a) scanf("%d", &a)
#define sal(a) scanf("%I64d", &a)
const int maxn = 1e6 + 5, INF = 0x3f3f3f3f;
int a[maxn];
long long dp[maxn], t[maxn];
int main (void)
{
    int n, m;
    while(~scanf("%d%d", &m, &n)){
        memset(dp, 0, sizeof(dp));
        memset(t, 0, sizeof(t));
        for(int i = 1; i <= n; i++)  sa(a[i]);
        long long ans;
        for(int i = 1; i <= m; i++){
            ans = -INF;
            for(int j = i; j <= n; j++){
                dp[j] = max(dp[j - 1], t[j - 1])+ a[j];
                t[j - 1] = ans;
                ans = max(ans, dp[j]);
            }
        }
        printf("%d
", ans);
    }
    return 0;
}
/* 1 2 2 3 3 3 -3 -3 -3 */