[백준]Baekjoon11054(Dynamic Programming)(LIS활용)

문제링크 : https://www.acmicpc.net/problem/11054

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int A[1001];
int B[1001];
int memo1[1001];
int memo2[1001];

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &A[i]);
		B[n + 1 - i] = A[i]; //A와 반대로 순서를 가진 수열 B를 만든다.
	}
	int max2 = 1;
	int max1 = 1;

	for (int i = 1; i <= n; i++) {
		memo1[i] = 1; //A의 memo
		memo2[i] = 1; //B의 memo
		for (int j = i-1; j >= 1; j--) {
			if (A[i] > A[j] && memo1[i] < memo1[j] + 1) {
				memo1[i] = memo1[j] + 1;
			}
			if (B[i] > B[j] && memo2[i] < memo2[j] + 1) {
				memo2[i] = memo2[j] + 1;
			}
		}
		//기존의 LIS 방식으로 각 배열의 수 까지의 최대 수열의 길이 구하는 과정
		if (memo2[i] > max2) max2 = memo2[i];
		if (memo1[i] > max1) max1 = memo1[i];
		//수열 자체가 아예 오름차순이거나 내림차순인 경우에
		//최대 수열의 길이를 구하는 과정
	}
	int result = max(max1, max2);
	max1 = 1; max2 = 1;
	// 수열 자체가 아예 오름차순이거나 내림차순인 경우
	// 결과값이 둘 중 하나기 때문에 max알고리즘 사용

	int num = 1;
	for (int i = 1; i <= n; i++) {
		if (memo1[i] > max1) {
			max1 = memo1[i];
			num = A[i];
		} // i까지 수열의 최장길이를 구한다.

		for (int j = 1; j <= n - i; j++) {
			//B는 A를 뒤집어 놓은 수열이므로
			// n-i까지의 배열중에 가장 큰 것을 판별하면 된다.
			// -> i이후의 내림차순 수열길이중 가장 큰 것을 판별하는 과정
			if (max1 + memo2[j] > result && B[j] != num)
				//B[j] != num을 추가해주는 이유는
				//만약 1 2 3 3 2 1 이라는 수열을 검사할 때
				//최장 길이를 6으로 인식할 수 있기 때문에
				//오름차순으로 1 2 3 이 최장 길이라는 것을 읽었을 때 
				//그 중 최댓값인 3을 내림차순 길이를 판별할 때는 제외하기 위함이다.
				result = max1 + memo2[j];
		}
	}
	printf("%d\n", result);
}