137. 11054(가장 긴 바이토닉 부분 수열)

import sys
input = sys.stdin.readline

N = int(input())
num = list(map(int,input().split()))
numReverse = num[::-1]

numDpIncrease = [1]*N
numDpDecrease = [1]*N

for i in range(N):
  for j in range(i):
    if num[i] > num[j]:
      numDpIncrease[i] = max(numDpIncrease[i], numDpIncrease[j]+1)
    if numReverse[i] > numReverse[j]:
      numDpDecrease[i] = max(numDpDecrease[i],numDpDecrease[j]+1)

result = [0]*N
for i in range(N):
  result[i] = numDpIncrease[i] + numDpDecrease[N-i-1]-1

print(max(result))

문제요약

가장 긴 바이토닉 부분 수열은?

S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열

설명

문제에 힌트가 있다.

S1 < S2 < ... Sk-1 < Sk 이 부분과

Sk > Sk+1 > ... SN-1 > SN 이 부분을 따로 생각해보자.

 

S1 < S2 < ... Sk-1 < Sk 이 부분은 0번째 인덱스 부터 증가하는 수열, 

Sk > Sk+1 > ... SN-1 > SN 아 부분은 N번째 인덱스 부터 증가하는 수열. 

 

따라서 

다음과 같이 입력값 | 입력값을 뒤집은 값을 나눈다.

 

수열을 진행하면서 해당 인덱스에서 가장 큰 길이를 가질 수 있는 것을 각각 정의해준다.

 

nomal에 해당 인덱스를 뒤집었기 때문에.

nomal[index] + reverse[N - index -1] 를 해준다면 1번과 2번을 합친 것이된다.

단, index 부분은 두 번 중복으로 수열을 처리했기 때문에 마지막에 -1을 해줘야 한다.

 

N = int(input())
num = list(map(int,input().split()))
numReverse = num[::-1]

값을 입력받고 뒤집어 주었다.

numDpIncrease = [1]*N
numDpDecrease = [1]*N

for i in range(N):
  for j in range(i):
    if num[i] > num[j]:
      numDpIncrease[i] = max(numDpIncrease[i], numDpIncrease[j]+1)
    if numReverse[i] > numReverse[j]:
      numDpDecrease[i] = max(numDpDecrease[i],numDpDecrease[j]+1)

두개의 리스트를 만들고. 

원래 리스트, 뒤집은 리스트에 해당 인덱스에 각각 가장 긴 수열을 계산해 주었다.

result = [0]*N
for i in range(N):
  result[i] = numDpIncrease[i] + numDpDecrease[N-i-1]-1

원래 값과 뒤집은 값을 더해 result를 에 저장해준다. 단, 계산과정 중 중복으로 처리한 부분이 있어 -1을 해준다.