[백준/C++] 11722번_가장 긴 감소하는 부분 수열

문제는 다음과 같습니다.

앞 문제의 증가하는 수열과 원리가 같습니다.
i번째 배열을 포함했을 때의 최대 감소 수열의 길이를 벡터 cnt에 담았습니다.
그래서 i번째의 cnt는 변수 j가 0부터 i-1까지 돌면서 최대의 cnt를 구하되,
이때의 전제조건은 감소수열이므로, a[j] > a[i] 이어야 합니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a[1000]={0, };
    vector<int> cnt;
    int n, tmp, j, cnt_max;
    cin>>n;
    cin>>tmp;
    a[0]=tmp; cnt.push_back(1);

    for(int i=1; i<n; i++){
      cin>>tmp; a[i]=tmp;

      j=i-1;
      cnt_max=0;
      while(j>=0){
        if(a[j]>tmp && cnt[j]>cnt_max) cnt_max=cnt[j];
        j--;
      }
      cnt.push_back(cnt_max + 1);
    }
    
    cout<<*max_element(cnt.begin(), cnt.end())<<endl;
    return 0;
}