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

LIS 문제에서 부등호 하나만 반대 부등호로 바꿔주면 된다.

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

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int* lds = new int[n];
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		int longestLength = 0;
		for (int j = 0; j < i; j++) {
			if (numbers[i] < numbers[j]) {
				if (lds[j] > longestLength)
					longestLength = lds[j];
			}
		}
		lds[i] = longestLength + 1;
		if (lds[i] > maxLength)
			maxLength = lds[i];
	}
	cout << maxLength;
	return 0;
}