[C++ / 11053] 가장 긴 증가하는 부분 수열

문제

11053번: 가장 긴 증가하는 부분 수열

---

문제 설명

수열 A가 주어졌을 때, 가장 긴 오름차순의 수열을 구하는 프로그램을 작성해야 한다.

---

풀이 방식

A = { 70, 30, 50, 60, 70, 0, 10}  다음과 같은 수열이 있다고 하자.

 

brute force식으로 구해보면 다음과 같다.

 

어떻게 해도 이 블로그 보다 설명을 잘 할 수 없으니 모르겠다면 참고 하도록 하자.

백준 11053번 가장 긴 증가하는 부분 수열 파이썬

 

---

솔루션

#include <iostream>
#include <vector>

using namespace std;

int arr[1001];
vector<int> dp(1001, 1);

int main()
{
  int n;
  cin >> n;

  for (int i = 0; i < n; i++)
    cin >> arr[i];

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < i; j++)
    {
      if (arr[i] > arr[j])
        dp[i] = max(dp[i], dp[j] + 1);
    }
  }

  int ans = 0;
  for (int i = 0; i < n; i++)
    ans = max(ans, dp[i]);

  cout << ans << endl;
}