백준 가장 긴 바이토닉 부분 수열

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

11054번: 가장 긴 바이토닉 부분 수열

여기서 포인트는 메모리 기억하는곳이 cnt1, cnt2 를 만들어준다음에 시작지점이 모두 1을 가지고 있어야한다는것을 기억해야합니다. 

그리고 그 시작 부분에서 현재 값을 비교하여 가장 큰 누적값을 합쳐서 다음을 계속 진행합니다. 그러면 가장 큰수로 갈것이고 그다음엔 반대 방향으로 가장 큰 수로 누적하면  이 두개의 메모리 값을 합치면 현재 최대로 긴 수열이 되겠죠 .

그리고 여기서 두 배열을 합치기 때문에 중복값을 1을 빼줍니다. 생각을 많이 해야하는 문제네요 ㅠ 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	//수열 s가 어떤 수 sk를 기준으로 
	//s1<s2<<s3<<s4 .... s> s
	//10 20 30 25 20
	//10 20 30 40 
	// {10, 20, 30, 40}, {50, 40, 25, 10} 
	int n;
	cin >> n;
	vector<int>lists;
	vector<int>cnts1(n, 1);
	vector<int>cnts2(n, 1);
	vector<int>anw;
	if (n == 1) {
		cout << 1;
		return 0;
	}
	
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		lists.push_back(tmp);
	}
	
	for (int i = 0; i < lists.size(); i++) {
		int maxs1 = 0;
		int maxs2 = 0;
		int indexi = (lists.size() - 1) - i;
		for (int j = 0; j < i; j++) {
			if (lists[i] > lists[j]) {
				maxs1 =max(maxs1, cnts1[j] + 1);
			}
			
			int indexj = (lists.size() - 1) - j;
			if (lists[indexi] > lists[indexj]) {
				maxs2 = max(maxs2, cnts2[indexj] + 1);
			}
		}
		cnts1[i] = max(maxs1, cnts1[i]);
		cnts2[ indexi ] = max( maxs2, cnts2[ indexi ]);
	}
	
	for (int i = 0; i < n; i++) {
		int tmpSum = cnts1[i]+ cnts2[ i ];
		anw.push_back(tmpSum);
	
	}
	sort(anw.begin(), anw.end(), greater<>());
	cout << anw[0] - 1;
	
	return 0;
}