HDU 1024 Max Sum Plus Plus DP

이 문제는 1003과 비슷하고 여러 가지 상태를 요구하는 것이기 때문에 DP의 사상으로 만든 것이 분명하다. 하지만......오랫동안 생각해 보았지만 DP를 어떻게 해야 좋을지 생각이 나지 않았습니다. 그리고 n의 값은 1000000에 달했고 매우 큽니다==그래요, 마지막에 인터넷에 접속해서 다른 신들의 DP 방법을 보고 나서야 이 문제를 어떻게 DP를 진행하는지 알게 되었습니다.DP를 할 때마다 머리가 어지러워요.
먼저 생각한 것은 하나의 2차원 그룹으로 DP를 진행하는 것이다. 2차원 그룹으로 몇 조를 기록하는 데 사용하고 다른 하나는 각 그룹의 최대 상황을 기록하는 데 사용한다. 구체적으로 어떻게 최대와 1003을 기록하면 똑같다. 그리고 n의 값이 비교적 크기 때문에 2차원으로 폭발할 것이다. 그래서 여기서 두 개의 그룹을 열어 2차원 그룹의 이 과정을 모의하고 DP를 진행한다. 아래 코드는

#include
#include
#include
#include
#include
using namespace std;
int dp[1000005];
int dm[1000005];
int a[1000005];

int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    int n,m;
    int i,j,t;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(dm,0,sizeof(dm));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=1;i<=m;i++)
        {
            t=INT_MIN;
            for(j=i;j<=n;j++)
            {
                dp[j]=max(dp[j-1]+a[j],dm[j-1]+a[j]);
                dm[j-1]=t;
                t=max(t,dp[j]);
            }
        }
        cout<