BOJ/백준 - 11053 가장 긴 증가하는 부분 수열 C++

수열을 입력받는다.

 

입력 받고, 1부터 N-1까지 찾아주는데,

이때 dp는 수열의 길이이다.

dp[i]는 1로 기본 설정을 해주고, for문들 돌리면서 이후 입력되는 값이 arr[j]보다 크면 dp[i]의 값을 그 작은 수의 수열의 길이+1과, 현재 dp[i]의 수열과 비교하여 설정해주고,

 

for문이 끝나면 if문을 하나 더 넣어주어 현재 수열의 값이 구해놓은 ans(wer)의 값보다 크다면 ans의 값을 update해준다.

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int dp[1001];
int arr[1001];
 
int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int N;
    int ans = 1;
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        dp[i] = 1;
 
        for (int j = 1; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
                cout << arr[j] << " ";
            }
        }
        if (dp[i] > ans) {
            ans = dp[i];
        }
 
    }
 
 
    cout << ans;
    
    return 0;
}