BOJ 11054. 가장 긴 바이토닉 부분 수열

• 1 번째 시도

1 번째 시도

• 점화식
  • dp[MAX_N][2]
  • dp[i][0] : i번째까지 증가하는 가장 긴 수열의 크기
  • dp[i][1] : i번째까지 감소하는 가장 긴 수열의 크기
  • dp[i][0] = max(dp[j][0] + 1) (단, 1 <= j < i, input[j] < input[i])
  • dp[i][1] = max(dp[j][0] + 1, dp[j][1] + 1) (단, 1 <= j < i, input[j] > input[i])
  • 초기값 : dp[i][0] = dp[i][1] = 1 (단, 1 <= i <= N)

1
2
3
4
5
6
7
8
9
10
11

	for (int i = 1; i <= N; i++)
		dp[i][0] = dp[i][1] = 1;

	for (int i = 2; i <= N; i++) {
		for (int j = 1; j < i; j++) {
			if (input[j] < input[i])
				dp[i][0] = max(dp[i][0], dp[j][0] + 1);
			else if (input[j] > input[i])
				dp[i][1] = max(dp[i][1], max(dp[j][0], dp[j][1]) + 1);
		}
	}