백준 11053 - 가장 긴 증가하는 부분 수열

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

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

문제 설명

---

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 

접근 방법

---

이 문제 같은 경우는 현재의 자신 값을 과거의 값들을 돌아봐서 그 중 최대의 값으로 자신의 최대 길이를 정하는 문제이다. 따라서 각 부분마다 과거의 저장한 배열을 검색을 해야한다.

 

 

코드

---

#include <iostream>
#include <vector>
using namespace std;
int n,cnt;
int number[1001];
int dp[1001];
int maxi;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>number[i];
    for (int i = 1; i <= n; i++){
        int mini = 0;
        for (int j = 0; j < i; j++){
            if (number[i]>number[j]){
                if (mini < dp[j]) mini = dp[j];
            }
        }
        dp[i] = mini + 1;
        if (maxi < dp[i])
            maxi = dp[i];
    }
    cout<<maxi<<"\n";
}

funny algorithm^^~