[ 백준 / C++ ] 11055 : 가장 큰 증가하는 부분 수열

[ 문제 ]

 

11055번: 가장 큰 증가하는 부분 수열 (acmicpc.net)

 

[ 접근방법 ]

 

n번째 입력을 마지막으로 하는 증가하는 부분 수열 중에서 가장 큰 합을 dt[n]에 저장하였다.

 

이중 for문을 돌면서 dt를 갱신해주면 된다.

 

n 최대 1000이므로 이렇게 풀어도 충분하다.

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

int n, a[1010], dt[1010], res;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    dt[0] = a[0];
    res = dt[0];
    for (int i = 1; i < n; i++)
    {
        int cnt = 0;
        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i] && cnt < dt[j])
                cnt = dt[j];
        }
        dt[i] = a[i];
        if (cnt)
            dt[i] += cnt;
        if (res < dt[i])
            res = dt[i];
    }

    cout << res;

    return 0;
}