[백준][11055번][DP] 가장 큰 증가 부분 수열

가장 큰 증가 부분 수열    

https://www.acmicpc.net/problem/11055

<코드>

#include <stdio.h>
 
int main(void){
    int N;
    int Dp[1010] = {};
    int A[1010] = {};
    int max = 0;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
        scanf("%d", &A[i]);
 
    for (int i = 1; i <= N; i++)
    {
        int maxDp = 0;
        for (int j = 0; j < i; j++){
            if (A[i]>A[j]){
                if (maxDp < Dp[j])
                    maxDp = Dp[j];
            }
        }
        Dp[i] = maxDp + A[i];
        if (max < Dp[i])
            max = Dp[i];
    }
 
    printf("%d\n", max);
 
}

<문제 푼 요령>

1. 이 문제 같은 경우는 푸는 방식이 이전글인 '가장 긴 증가 부분 수열' 과 동일하다. 

2. 그 문제와 차이점은 Dp[i] 배열에 넣는 값이 수열의 길이가 아닌 최대합을 집어 넣어야하기 때문에 그 집어넣는 값을 A[i] 배열의 값을 더해서 주면 된다.