[백준 11055번] 가장 큰 증가 부분 수열 (C++)

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

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

---

가장 큰 증가 부분 수열은 n이 최대 1,000이므로 백트래킹을 이용하는 경우 시간초과가 발생할 수 있습니다. 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 

 

부분 수열의 첫 원소는 어느 숫자든 가능하며, 이후의 원소는 이전 원소보다 커야합니다.

따라서 시작 원소 이후, 첫 원소보다 큰 원소들에 대해 가장 큰 증가 부분 수열의 합을 계산하고, 그 중에서도 가장 큰 합과 시작 원소를 더해주면 가장 큰 증가 부분 수열의 합을 계산할 수 있습니다.

또한 앞서 언급한 것처럼, 어느 원소든 시작점이 될 수 있기 때문에 위와 같은 연산을 모든 원소에 대해 수행해주면 됩니다.

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int arr[1001], d[1001];
int n;

int sum(int idx){   // idx부터 시작하여 가장 큰 증가 부분 수열의 합을 반환하는 함수
    if(d[idx] != 0)
        return d[idx];
    else{
        int ans = INT_MIN;    // idx번째 원소를 제외한 나머지 가장 큰 수열의 합
        bool biggest = true;    // idx 이후로 arr[idx]보다 큰 원소가 있는지를 나타내는 flag
        for(int i = n - 1; i > idx; i--){
            if(arr[idx] < arr[i]){
                biggest = false;    // idx 이후로 arr[idx]보다 큰 원소가 있음
                ans = max(ans, sum(i)); // arr[idx]보다 큰 원소를 시작점으로 가장 큰 증가 부분 수열의 합을 계산
            }
        }

        if(biggest) d[idx] = arr[idx]; // idx 이후로 arr[idx]보다 큰 것이 하나도 없다면, idx부터 시작하여 가장 큰 증가 부분 수열의 합은 자기 자신 뿐
        else d[idx] = arr[idx] + ans; // 그렇지 않다면 가장 큰 
        return d[idx];
    }
}

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

    for(int i = 0; i < n; i++) cin >> arr[i];   // 수열 입력 받음
    for(int i = 0; i < n; i++) sum(i);  // 수열의 각 원소를 시작점으로 잡고, 가장 큰 증가 부분 수열의 합을 구함

    cout << *max_element(d, d + 1001);  // 시작점에 따른 가장 큰 증가 부분의 수열 중 가장 큰 합을 출력
}

 

아래는 문제 풀이에 사용된 테스트 케이스입니다.

4
3 1 2 3
-> 6

7
2 1 100 97 98 99 101
-> 397