백준 11722: 가장 긴 감소하는 부분 순열

가장 긴 증가하는 부분 순열과 비슷하지만 약간의 트릭으로 스택에 수열을 넣고 다시 빼놓아서 뒤집어주고 동일한 방법으로 가장 긴 증가하는 부분 순열을 구하면 된다. 스택에 들어간 일련의 원소들은 순서가 뒤집어주는 성질이 있다. 유용하게 사용하자

 
#include <iostream>
#include <algorithm> 
#include <stack>
using namespace std; 
int d[1050];
int seq[1050];
stack<int> make_reverse;
int main() 
{
    int input = 0;
    cin >> input;
    for (int i = 1; i <= input; ++i)
    {
        cin >> seq[i];
        make_reverse.push(seq[i]);
    }
    for (int i = 1; i <= input; ++i)
    {
       seq[i] = make_reverse.top();
        make_reverse.pop();
    }
    for (int i = 0; i <= input; ++i)
        d[i] = 1;
    for (int i = 2; i <= input; ++i)
    {
        for (int j = 1; j < i; ++j)
        {
            if (seq[i] > seq[i - j])
                d[i] = max(d[i], d[i - j] + 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= input; ++i)
        ans = max(ans, d[i]);
    cout << ans;
    return 0;
 
}