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

문제

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

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

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int n;
int arr[1001];
int dp[1001];
int main() {
  cin >> n;
  for(int i = 0;i<n;i++){
    cin >> arr[i];
  }
  int max = 0;
  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];
    }
    if(max<dp[i]) max = dp[i];
  }
  cout << max << endl;
}