[python/11054]가장 긴 바이토닉 부분 수열

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

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

이 문제는 '가장 긴 증가하는 부분 수열' 문제를 응용한 것입니다.

 

https://onlab94.tistory.com/54

[python/11053]가장 긴 증가하는 부분 수열

'가장 긴 증가하는 부분 수열'의 경우는 배열을 정방향으로 한 번만 검사하여 증가하는 부분의 길이를 찾으면 됐었습니다.

하지만 이번 문제의 경우는 정방향으로 증가하는 부분의 길이를 구하고 역방향으로 증가하는 부분의 길이를 구한 후 값을 더하면 가장 긴 바이 토닉 부분 수열의 길이를 구할 수 있습니다.

여기서 주의할 점은 정방향과 역방향의 길이를 더한 후 최댓값이 중복되기 때문에 더한 값에서 -1을 해주어야 합니다.

 

코드를 보시려면 더보기를 클릭하시면 됩니다.

가장 긴 바이 토닉 부분 수열

 

def solve(N, LIS):
    dp = [1] * N
    dp_increase = [1] * N
    dp_decrease = [1] * N
    for i in range(N):
        for j in range(i):
            if LIS[i] > LIS[j]:
                dp_increase[i] = max(dp_increase[i], dp_increase[j] + 1)
 
    for i in range(N-1, -1, -1):
        for j in range(N-1, i, -1):
            if LIS[i] > LIS[j]:
                dp_decrease[i] = max(dp_decrease[i], dp_decrease[j] + 1)
        dp[i] = dp_increase[i] + dp_decrease[i]
 
    return max(dp) - 1
 
if __name__=='__main__':
    N = int(input())
    LIS = list(map(int, input().split()))
    print(solve(N, LIS))