C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 11053번:가장 긴 증가하는 부분 수열 답

//가장 긴 증가하는 부분수열의 길이를 D

//D[i] = A[1],A[2],...,A[i]; i가 마지막으로 수열이 끝날 때의 D의 길이 = D[i]

//A[i]>A[j] 이고 D[j] > D[i] 일 때 D[i] = D[j]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i<n; i++) {
        cin >> A[i];
    }
    vector<int> D(n);
    for (int i = 0; i<n; i++) {
        D[i] = 1;
        for (int j = 0; j<i; j++) {
            if (A[j] < A[i] && D[j] + 1 > D[i]) {
                D[i] = D[j] + 1;
                
            }
            
        }
        
    }
    cout << *max_element(D.begin(), D.end()) << '\n';//배열의 처음부터 끝까지 살펴본 뒤 그 중 가장 큰 값을 출력
}