백준 11054

https://www.acmicpc.net/problem/11054

이  문제의경우 LIS 를 사용할 줄 알면 쉬운 문제이다
그후 LIS의 값과 뒤의 인덱스부터의 LIS

#include <iostream>
using namespace std;
int arr[1000] = { 0, };
int n;
int ascendingNum[1001];
int descendingNum[1001];
int maxNum=0;
void getAsc() {
	for (int i = 1; i <= n; i++) {
		ascendingNum[i] = 1;
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j]) {
				ascendingNum[i]=max(ascendingNum[j] + 1,ascendingNum[i]);
			}
		}
	}
}


void getDsc() {
	for (int i = n; i > 0; i--) {
		descendingNum[i] = 1;
		for (int j = n; j > i; j--) {
			if (arr[i] > arr[j]) {
				descendingNum[i] = max(descendingNum[j] + 1, descendingNum[i]);
			}
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	getAsc();
	getDsc();
	for (int i = 1; i <= n; i++) {
		if (ascendingNum[i]+descendingNum[i] > maxNum) {
			maxNum = ascendingNum[i] + descendingNum[i];
		}
	}

	cout << maxNum-1;
}

의 값의 합이 최댓값이 되는 부분을 고른후 -1 해주면 된다 -1을 하는 이유는 해당 방식으로 순열을 고르면 그 범위에서  수가 겹침으로 1개를 빼주는 것이다 41퍼대에서 에러가났는데 그 이유는 dp 배열을 1001로해야하는데 1000으로 해서 틀렸었다

LIS 를 설명 하자면
우리 의 테스트 케이스를 리스트로 넣어보자

이렇게 될것이다 왼쪽 아래에 0을 넣은 이유는 1이전에는 증가하는 수열이 0이기 때문에 넣었다

그리고 1까지 가장 긴  증가하는 순열을 1이다

5일 때는 2이다

 

자 이제 2일 때를 보자 2일때 가장 증가하는 부분순열은 나 이전에 나보다 작은 애까지의 부분순열의 최댓값을 넣어 주면 된다 즉 나의 이전에 값들중 나보다 작은 값들의 증가하는 부분순열의 최대값들을 더하는 것이다 예시로 더 설명 하도록 하겠다

완성된 그림을 보자 뒤에서 부터 2번째의 5를 보자 얘보다 작은 애들중 가장  큰인덱스는 8번째인덱스의  4이다 해당인덱스의 나를 붙이면 해당 사이즈의 +1이 되기에 5이다