HDU 1024 Max Sum Plus Plus(일부 하위 구간 최대)

사고방식: 이 유형의 문제에 대해 다음과 같은 몇 가지 측면에서 분석할 수 있다.
   1.현재의 수를 삽입점으로 하고, 단지 두 가지 상황 (1) 현재의 수를 단독으로 하나의 구간에 새로 놓는다.(2) j-1과 같은 구간에 넣는다.그러면 우리는 dp[i][j]로 앞의 j개수에 i개의 구간을 구분했다는 것을 나타낼 수 있다.고유상태 전이 방정식: dp[i][j]=max(dp[i-1][j-1], dp[i][j-1])+a[j];m의 범위가 제시되지 않았기 때문에 dp[m][n]의 수조를 열 수 없습니다.그렇다면 최적화된 방안이 필요하다.스크롤 그룹의 최적화 방식과 유사하게 두 개의 그룹을 열 수 있는데 각각pre[]이고 now[]는 전 그룹과 현재 그룹의 숫자와 상황을 대표한다.그러면 새로운 수를 넣을 때 전 조에 넣을지 현재 조에 넣을지 판단해야 한다.pre[] 그룹을 계속 업데이트합니다.(왜%I64dWA-!)

#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define L int
using namespace std;

L now[1000100],pre[1000100],a[1000100];

int main()
{
    int n,m,i,j,k;
    while(~scanf("%d%d",&m,&n))
    {
        for(i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            now[i]=pre[i]=0;
        }
        now[0]=pre[0]=0;
        L ma;
        for(i=1; i<=m; i++)
        {
            ma=-0x3f3f3f3f;
            for(j=i; j<=n; j++)
            {
                now[j]=max(now[j-1],pre[j-1])+a[j];
                pre[j-1]=ma;
                if(now[j]>ma)
                {
                    ma=now[j];
                }
            }
           // pre[j-1]=ma;
        }
        printf("%d
",ma);
    }
    return 0;
}