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

문제

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

풀이과정

증가하는 부분 수열 (A[j]<A[i]) 중에서 현재 비교값 (DP[i]이 이전번째까지의 합 DP[j] + 자신의 값(A[i]) 보다 작을 때, DP[i] = DP[j] + A[i] 를 해준다.

소스코드

#include <iostream>
 
int A[1001],DP[1001];
 
int main()
{
    int N,max=0;
 
    std::cin >> N;
 
    for (int i = 1; i <= N; i++) std::cin >> A[i];
 
    for (int i = 1; i <= N; i++)
    {
        DP[i] = A[i];
        for (int j = 1; j < i; j++)
        {
            if (A[j] < A[i] && DP[i] < DP[j] + A[i])
                DP[i] = DP[j] + A[i];
        }
        if (max < DP[i]) max = DP[i];
    }
 
    std::cout << max;
 
    return 0;
}