Longest Decreasing Subarray

맞은 문제 다른 풀이방법 복기

가장 긴 (감소하는 부분수열) = 가장 긴 (뒤에서부터 증가하는 부분수열)

A[ i ] 뒤에 A[ j ]가 있고 i < j, A[ i ] > A[ j ]일 때 뒤에서부터 증가하는 부분수열의 길이를 구하면 된다.

for (int i=n; i>=1; i--) {
    d[i] = 1;
    for (int j=i+1; j<=n; j++) {
        if (a[i] > a[j] && d[i] < d[j]+1) {
            d[i] = d[j]+1;
        }
    }
}