BOJ 11722 가장 긴 감소하는 부분 수열

boj 11722 가장 긴 감소하는 부분 수열

boj 11053 풀이 보기
boj 11053 문제에서 증가하냐 감소하냐의 차이만 있을 뿐 다른 것은 다 똑같은 문제이다. 그렇기에 점화식을 실행하는 2가지 조건 중 a[i] > a[j]만 a[i] < a[j]로 바꿔주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[1005];
int D[1005];
int mx;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    for (int i = 1; i <= n; i++)
    {
        D[i] = 1;

        for (int j = 1; j < i; j++)
        {
            if (a[i] < a[j] && D[j] >= D[i])
                D[i] = D[j] + 1;
        }
        mx = max(mx, D[i]);
    }

    cout << mx;
}