백준 17216, 가장 큰 감소 부분 수열

개요

문제 링크
실버 1, DP

최장 감소 수열을 구하는 문제, 만약 여러 개가 있으면 합이 가장 큰 수열의 합을 출력한다.

---

접근

1. N = 1000이므로 O(N^2)으로 접근 가능
2. dp를 사용한다. 저장할 값은 i 번째까지의 최대합이다.
3. 갱신은? 앞큰수를 발견하면 max(현재 저장된 값, 새로 갱신될 값)을 해주면 된다.
4. 새로 갱신될 값은? 앞큰수에 현재값을 더한 값이 되겠다.
   즉 과거의 최대합 + 자신의 값이 저장된 값보다 더 큰 경우 갱신

---

Pseudo code

dp[i] = max_sum_value;
if (앞큰수 발견)
    new_sum_value = dp[앞큰수]+a[i]
    dp[i] = max(dp[i],new_sum_value)

---

Source code

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

int main() {
    int n;
    cin >> n;
    int a[n+1];
    for (int i=1; i<=n; i++)
        cin >> a[i];
    int dp[n+1];
    dp[0] = 0;
    for (int i=1; i<=n; i++)
        dp[i] = a[i];
    for (int i=1; i<=n; i++)
        for (int j=0; j<i; j++)
            if (a[j] > a[i])
                dp[i] = max(dp[i], dp[j]+a[i]);
    int ans = 0;
    for (int i=1; i<=n; i++)
        ans = max(ans, dp[i]);
    cout << ans;
}