11055번 : 가장 큰 증가 부분 수열 -Python

문제

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

풀이

수열 A에서 각 자리에서 더할 수 있는 최대 합을 계산한 뒤 가장 큰 합을 출력하면 된다.

각 자리에서 최대의 수를 계산하는 방법은 A[i]가 A[i-1]보다 크다면 i에서의 최대 합은 A[i]+A[i-1]이 될것이다.

하지만 무조건 A[i]+A[i-1]이 큰 경우는 아니다. 반례로 A ={10, 20, 10, 30}일 경우 A[3]에서의 최대 값은 A[3]+A[2]인 40이 아니라 A[0]+A[1]+A[3]인 60이다.

이 경우를 해결하는 방법은 A[3]을 A[0]~A[2]까지 비교해서 A[3]보다 작은 수들을 더한 값과 A[2]중에서 큰 값을 A[3]에 더한 값을 최대 합으로 해주면 된다.

코드

from sys import stdin, stdout

input = stdin.readline 

n = int(input())

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

dp = [0 for i in range(n)]

for i in range(n):
    dp[i] = array[i]
    for j in range(i):
        if array[i] > array[j]:
            dp[i] = max(array[i]+dp[j],dp[i])
            #array[i]+dp[j] 와 dp[i]를 비교하는 이유는 전의 숫자를 더한다고 무조건 최대 합이 나오는게 아니기 때문이다.

print(max(dp))

비슷한 문제

11053번 : 가장 긴 증가하는 부분 수열 / 풀이
11054번 : 가장 긴 바이토닉 부분 수열 / 풀이
12015번 : 가장 긴 증가하는 부분 수열 2 / 풀이