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

www.acmicpc.net/problem/11053

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

BOJ 11722 - 가장 긴 감소하는 부분 수열  (sdy-study.tistory.com/160)

과 똑같은 문제다

 

감소하는것 대신 증가하는것 찾으면 되니

부등호만 바꾸면 된다.

 

 

- c++

#include <iostream>
 
#define MAX 1001
 
using namespace std;
 
int N, answer;
int arr[MAX], dp[MAX];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> arr[i];
    
    for (int i = 0; i < N; ++i) {
        dp[i] = 1;
        for (int j = 0; j <= i; ++j) {
            if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }
    
    for (int i = 0; i < N; ++i)
        if (answer < dp[i])
            answer = dp[i];
            
    cout << answer;
    
    return 0;
}