백준 11054번 C++

#include <iostream>

#include <algorithm>

using namespace std;

const int MAX = 1001;

int n;

int arr[MAX];

int lisnum[MAX];

int LIS(int k) {

for (int i = 0; i <= k; i++) {

lisnum[i] = 1;

for (int j = 0; j < i; j++) {

if (arr[i] > arr[j] && lisnum[i] < lisnum[j] + 1)

lisnum[i] = lisnum[j] + 1;

}

}

int answer = lisnum[k];

for (int i = n-1; i >= k; i--) {

lisnum[i] = 1;

for (int j = n-1; j > i; j--) {

if (arr[i] > arr[j] && lisnum[i] < lisnum[j] + 1)

lisnum[i] = lisnum[j] + 1;

}

}

return answer + lisnum[k] - 1;

}

int main(void) {

cin >> n;

for (int i = 0; i < n; i++) {

cin >> arr[i];

}

int answer = -1;

for (int i = 0; i < n; i++) {

answer = max(answer, LIS(i));

}

cout << answer;

return 0;

}