백준11055. 가장 큰 증가하는 부분 수열 (DP)

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

11055번: 가장 큰 증가하는 부분 수열

n<= 1000이므로 O(n^2)의 알고리즘을 짜면 해결할 수 있다. 

dp 테이블인 d를 i를 포함하는 부분 집합의 최대합으로 설정한다. 때문에, d는 초기값을 들어온 값으로 설정할 수 있다. 

(d의 최솟값은 현재 좌표만을 부분 집합으로 가질때이다.)

 

나는 이 테이블 정의하는 데에서 시간이 오래 걸렸다. (i 까지의 부분 집합의 최대합이라고 정의했기 때문)

아무튼 이렇게 테이블을 설정하고, 이중 for문을 돌면서 현재 좌표를 포함하는 부분 집합의 최댓값을 업데이트 해주면된다. 

 

코드는 다음과 같다. 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <limits.h>
#include <algorithm>
using namespace std;

int n;
int arr[1002];
int d[1002]; // i를 포함하는 부분 집합의 최대합
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
        d[i] = arr[i];
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(arr[i] > arr[j]) d[i] = max(d[j]+arr[i], d[i]);
        }
    }
    
    cout << *max_element(d, d+n);

}