백준 11054번 C++

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAX = 1001;
int n;
int num[MAX];
int decreasing[MAX],increasing[MAX];

int increase(int k){
	for (int i = 0; i <= k; i++) {
		if (increasing[i] != 0)
			continue;
		for (int j = i - 1; j >= 0; j--) {
			if (num[i] > num[j]) {
				increasing[i] = max(increasing[i], increasing[j]);
			}
		}
		increasing[i] += 1;
	}
	return increasing[k];
}

int decrease(int k) {
	for (int i = n-1; i >=k; i--) {
		if (decreasing[i] != 0)
			continue;
		for (int j = i + 1; j < n; j++) {
			if (num[i] > num[j]) {
				decreasing[i] = max(decreasing[i], decreasing[j]);
			}
		}
		decreasing[i] += 1;
	}
	return decreasing[k]-1;
}

int main(void) {
	int answer = -1;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		cin >> num[i];

	memset(decreasing, 0, sizeof(decreasing));
	memset(increasing, 0, sizeof(increasing));
	increasing[0] = 1;
	decreasing[n - 1] = 1;
	for (int i = 0; i < n; i++) {
		answer = max(answer, increase(i) + decrease(i));
	}
	cout << answer << endl;
	return 0;
}