poj 8464 주식 매매(dp/분할)

poj8464 주식 매매(dp/분할) 프로그램 설계 실습 15년 기말고사 난제 총 시간 제한: 1000ms 메모리 제한: 65536kB
최근 점점 더 많은 사람들이 주식시장에 투신하고 있다는 묘사에 아푸도 약간 설레었다."주식시장에 위험이 있으니 입시는 신중해야 한다"는 것을 명심하고, 아푸는 먼저 간략한 주식 매매 문제를 연구하기로 결정했다.
가령 아포가 어떤 주식의 미래 N일의 가격을 정확하게 예측했다고 가정한다면, 그는 두 번 매매하여 얻은 이윤이 가장 높기를 희망한다.간단하게 계산하기 위해 이윤의 계산 방식은 매도 가격에서 매입 가격을 줄이는 것이다.
같은 날 여러 차례 매매가 가능하다.하지만 첫 번째 매입 이후 먼저 팔아야 두 번째 매입이 가능하다.
현재, 아포는 그가 가장 많은 이윤을 얻을 수 있는지 알고 싶어 한다.
입력한 첫 번째 행은 T그룹 데이터가 모두 있음을 나타내는 정수 T(T <= 50)입니다.다음 데이터 세트의 첫 번째 행은 총 N일을 나타내는 정수 N(1 <= N <= 100, 000)입니다.두 번째 줄은 빈칸에 의해 분리된 N개의 정수로 매일 이 주식의 가격을 나타낸다.이 주식의 매일 가격의 절대치는 모두 1000000을 넘지 않을 것이다.
출력은 각 그룹의 데이터에 대해 한 줄을 출력합니다.그 은행은 아푸가 얻을 수 있는 가장 큰 이윤을 나타내는 정수를 포함하고 있다.
샘플 입력
3 7 5 14 -2 4 9 3 17 6 6 8 7 4 1 -2 4 18 9 5 2
샘플 출력
28 2 0
제시된 1조 사례에 대해 아푸는 1일 차 매입(가격 5)한 뒤 2일 차 매도(가격 14)할 수 있다.두 번째는 3일째(가격-2)를 사들인 뒤 7일째에 팔았다(가격17).모두 얻은 이익은 (14-5)+(17-(-2) = 28이다. 2조 사례에 대해 아푸는 1일 차 매입(가격 6)한 뒤 2일 차 매도(8)할 수 있다.두 번째는 여전히 이튿날 사들인 뒤 이튿날 팔았다.모두 얻은 이윤은 8-6=2로 3조 사례에 대해 가격이 계속 떨어지기 때문에 아포는 마음대로 하루를 선택하여 매입한 후에 신속하게 팔 수 있다.얻은 최대 이윤은 0이다
이 문제는 욕심인 줄 알았는데 오랫동안 생각해 봤는데 분치+dp였다.두 차례의 매매로 나누어 처리할 수 있다. ans=max{f[i][1][0]+f[1][1]]],\1<=i<=n
f[i][0][j]: i 전(후) 접미사 거래 최대치 포함, f[i][1][j]: f[i][0][j] 전(후) 접미사 최대치
그중 j=0 접두사;j=1 접미사
그러나 이렇게 하면 TLE가 된다. 알고리즘은 이미 거의 최적화되지 않았지만 작은 문제가 생겼다.
f[i][0][j]는 저장할 필요가 없고 마지막 값만 저장하면 된다. 수조로 기록하면 공간을 낭비할 뿐만 아니라 액세스 공간을 분배하여 시간을 낭비하기 때문에 TLE를 할 수 있기 때문에 반드시 세밀하게 해야 한다. 그래서 불필요한 데이터 저장과 불필요한 절차를 최적화해야 한다.

Accepted    10  2632kB  690ms   920 B   G++

#define MAX_N 1000000

#include<stdio.h>

int cases,n,ans,p[MAX_N],d[MAX_N];
int f[MAX_N][2],max_now;
/* * f[i][j]: i ( )       * j=0,  ;j=1,   */

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

int main()
{
    scanf("%d",&cases);
    while (cases--)
    {
        scanf("%d",&n);
        for (int i=0;i<n;i++)
            scanf("%d",&p[i]);
        for (int i=0;i<n-1;i++)
            d[i]=p[i+1]-p[i];
        max_now=0;
        f[0][0]=0;
        for (int i=0;i<n-1;i++)
        {
            max_now=max(0,max_now+d[i]);
            f[i+1][0]=max(f[i][0],max_now); 
        }
        max_now=0;
        f[n-1][1]=0;
        for (int i=n-2;i>=0;i--)
        {
            max_now=max(0,max_now+d[i]);
            f[i][1]=max(f[i+1][1],max_now); 
        }
        /*
        for (int i=0;i<n;i++)
            printf("%3d ",f[i][0]);
        printf("
");
        for (int i=0;i<n;i++)
            printf("%3d ",f[i][1]);
        printf("
");
        */
        ans=0;
        for (int i=0;i<n;i++)
            if (f[i][1]+f[i][0]>ans)
                ans=f[i][1]+f[i][0];
        printf("%d
",ans);
    }
    return 0;
}