[백준] 11054번 : 가장 긴 바이토닉 부분 수열

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

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

위의 문제는

https://bigkwangs.tistory.com/28

[백준] 12015번 : 가장 긴 증가하는 부분 수열 2

해당문제를 leftarr와 rightarr로 쪼개어 길이를 계산하여 더하였다.

1. leftarr 는 해당 인덱스보다 작은 수열 길이를 구한다.

2. rightarr은 해당 인덱스보다 큰 수열의 길이를 구한다.

3. leftarr와 rightarr에서 자기자신은 2번이 중첩됨으로, -1를 한값의 최대값을 구한다.

from bisect import bisect_left
N = int(input())
arr = list(map(int, input().split()))

maxvalue = 0
for i in range(N):
    leftarr = arr[:i+1]
    rightarr = arr[i:]
    
    
    temp = [leftarr[0]]
    for j in range(len(leftarr)):
        if leftarr[j] > temp[-1]:
            temp.append(leftarr[j])
        else:
            idx = bisect_left(temp, leftarr[j])
            temp[idx] = leftarr[j]
            
    rightarr.reverse()
    temp2 = [rightarr[0]]
    for j in range(len(rightarr)):
        if rightarr[j] > temp2[-1]:
            temp2.append(rightarr[j])
        else:
            idx = bisect_left(temp2, rightarr[j])
            temp2[idx] = rightarr[j]
            
    maxvalue = max(maxvalue, len(temp)+len(temp2) -1)

print(maxvalue)