[BOJ S2][C++] 백준 11053번: 가장 긴 증가하는 부분 수열

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

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

 

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lis(int n, vector<int>&a) {
    vector<int>dp (n,1);  // dp[i] : a[i]로 끝나는 가장 큰 수열
    
    for(int i=0; i<n; i++){
        int tmpMax = 0;
        
        for(int j=0; j<i; j++) {
            if(a[j]<a[i] && tmpMax<dp[j])
                // 현재 수 a[i]보다 작은 숫자를 찾고 해당 숫자가 전까지의 문자열 갯수 dp[j] 의 최댓값찾기
                tmpMax = dp[j];
        }
        
        dp[i] += tmpMax;
    }
    
    int maxDp = *max_element(dp.begin(), dp.end());
    
    return maxDp;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for(int i=0; i<n; i++)
        cin >> a[i];
    
    cout << lis(n, a);
    
    return 0;
}

/*
 */