[백준] 11054번(python 파이썬)

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

 

 

dp1

리스트 A의 i : 0 ~ n-1 에서의 증가하는 수열의 값을 구한다.

 

dp2

리스트 A의 i : n-1 ~ 0 에서의 증가하는 수열의 값을 구한다.

 

ex)

 

dp3

dp3[0] = dp2[0]

dp3[n-1] = dp1[n-1]

 

리스트 A의 i :1 ~ n-2 에서

1. 리스트 A의 j : 1 ~ i 부분에서 a[i] 보다 작은 값중에서 최대값 dp1[j] 을 찾는다.

2. 리스트 A의 j : i ~ n-2 부분에서 a[i] 보다 작은 값중에서 최대값 dp2[j] 을 찾는다.

dp3[i] = 1번과 2번을 더한후 1을 더해준다.

 

 

n = int(input())
a = list(map(int, input().split()))
reverse_a = list(reversed(a))

inc_dp = [0] * n
dec_dp = [0] * n
dp = [0] * n

def incSequence():
    inc_dp[0] = 1
    for i in range(1, n):
        max_temp = 0
        for j in range(i):
            if a[i] > a[j]:
                max_temp = max(max_temp, inc_dp[j])
        inc_dp[i] = max_temp + 1

def decSequence():
    dec_dp[0] = 1
    for i in range(1, n):
        max_temp = 0
        for j in range(i):
            if reverse_a[i] > reverse_a[j]:
                max_temp = max(max_temp, dec_dp[j])
        dec_dp[i] = max_temp + 1

def bitonic():
    for i in range(n):
        max_left_temp = 0
        max_right_temp = 0

        if i == 0:
            dp[i] = dec_dp[i]
            continue
        if i == n-1:
            dp[i] = inc_dp[i]
            continue

        for j in range(i):
            if a[i] > a[j]:
                max_left_temp = max(max_left_temp, inc_dp[j])

        for k in range(i+1, n):
            if a[i] > a[k]:
                max_right_temp = max(max_right_temp, dec_dp[k])

        dp[i] = max_left_temp + max_right_temp + 1


incSequence()
decSequence()
dec_dp.reverse()
bitonic()

print(max(dp))