BOJ)11055 가장 큰 증가 부분 수열

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

arr[0] ~ arr[i] (i=0~n) 에 대하여 값의 합들이 가장 큰 것을 dp 배열에 저장해가며 진행합니다.

#include <iostream>
using namespace std;
 
int arr[1001];
long long dp[1001];
int main()
{
    int n;
    long long result = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[i] < dp[j] + arr[i]) {
                dp[i] = dp[j] + arr[i];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        result = result < dp[i] ? dp[i] : result;
    }
    cout << result;
 
}