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

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

문제 링크

int N;
int dp[1004];
int numbers[1004];
void input() {
  cin >> N;
  for(int i=0; i<N; i++) {
    cin >> numbers[i];
  }
}
void solve() {
  int answer = 0;
  for(int i=0; i<N; i++) {
    dp[i] = numbers[i];
    for(int j=0; j<i; j++) {
      if(numbers[i] > numbers[j] && dp[i] < dp[j] + numbers[i]) { //
        dp[i] = numbers[i] + dp[j];
      }
    }
    answer = max(answer, dp[i]);
  }
  
  cout << answer << endl;
}
int main() {

  input();
  solve();

  return 0;
}