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

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

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

---

•  i 번째 위치까지의 증가 부분 수열의 최대 합은, 1 부터 i-1 까지의 증가 부분 수열들 중 i 번째 위치를 증가 부분 수열로 포함시키는 수열의 최대 합 + i 번째 값이 된다.
• i 번째 위치가 증가 부분 수열로써 포함되지 않을 수 있기 때문에, i 번째 최대 합이 전체 부분 수열들 중 최대값이 되는 것은 아니다.
• 1 부터 i 까지의 최대 합을 구해나가면서 각 수열의 최대합들 중 최댓값을 구해준다.

---

#include <iostream>

using namespace std;

int N, answer;
int arr[1001];
int ans[1001];

int main(void)
{
    cin >> N;
    for(int i = 1 ; i <= N ; i++) cin >> arr[i];

    for(int i = 1 ; i <= N ; i++)                   // 각 인덱스의 최대 증가 수열 값을 구함
    {
        int maxi = 0;                               // 이번 인덱스값보다 작은 값들 중 최대합
        for(int idx = 1 ; idx < i ; idx++)
        {
            if(arr[idx] < arr[i] && ans[idx] > maxi)    // 증가 부분 수열이 되기 위해, 이번 인덱스값보다 작은 값이어야 함
            {
                maxi = ans[idx];                        // 해당 인덱스들 중 최대합을 갖는 값
            }
        }
        ans[i] = maxi + arr[i];                     // 이번 라운드에 갱신가능한 이전까지의 최댓값 + 현재값
        if(answer < ans[i]) answer = ans[i];        // 최댓값 갱신해줌
    }

    cout << answer << endl;
}