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

def find_lis(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
def find_lds(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if array[i] < array[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
        




N = int(input())

arr = list(map(int,input().split()))

lis_dp = find_lis(arr)
result = 0
for ind in range(N):
    lds_dp = find_lds(arr[ind:])
    result = max(result,lis_dp[ind] + max(lds_dp) -1)
print(result)

처음에 푼 방식이다. 먼저 가장 긴 증가 부분 수열의 길이를 구하고 난뒤,

 

각 index마다 잘라서 가장 긴 감소 부분 수열을 구해서 더해주었다.

 

이러한 방식으로 푸니깐 시간이 오래걸렸다.

 

 

def find_lis(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
def find_lds(array):
    dp = [0]*len(array)

    for i in range(len(array)-1,-1,-1):
        dp[i] = 1
        for j in range(i+1,len(array)):
            if array[i] > array[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
        




N = int(input())

arr = list(map(int,input().split()))

lis_dp = find_lis(arr)
lds_dp = find_lds(arr)

result = 0
for ind in range(N):
    result = max(result,lis_dp[ind]+lds_dp[ind]-1)
print(result)

그 다음으로 푼 방식이다.

 

LIS를 두군데로 해서 구해주었다.

 

앞에서 가장 긴 뒤에서 가장 긴 증가 부분수열을 구해주었다.

 

긴 바이토닉 부분 수열을 보면 가운데를 중심으로 좌측에서는 긴 증가부분 수열이고, 우측은 감소부분수열인데, 이걸 역으로 보면 우측을 거꾸로 돌리면 증가 부분 수열이 된다.

 

이러한 점을 이용해 좌측에서부터의 긴 증가부분 수열과 수열을 거꾸로 해서 긴 증가부분 수열의 길이를 구해, 서로 더해주면 긴 바이토닉 부분 수열이 나온다.