[C++] BOJ 11055 가장 큰 증가하는 부분 수열

문제 출처

백준 온라인 저지

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

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

 

문제 

 

입 / 출력

 

풀이

LIS(Longest Increasing Subsequence) 라는 유명한 유형의 문제이며, DP를 활용해서 푸는 문제이다

 

수열의 특성을 이용해서 

• 각각의 값이 이전 값보다 작고, (seq[j] < seq[i])  
• 그 중에서 가장 큰 값 (dp[i] = max(dp[i], dp[j]+seq[i]);)

을 통해서 가장 긴 부분 수열을 구할 수 있다.

 

코드

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX = 1001;
int dp[MAX], seq[MAX];
int N, result = 0;

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> seq[i];
    dp[i] = seq[i];
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < i; j++) {
      if (seq[j] < seq[i])
        dp[i] = max(dp[i], dp[j] + seq[i]);
    }
    result = max(result, dp[i]);
  }

  cout << result << "\n";
}