[백준 실버 1912 동적프로그래밍] 연속합문제 파이썬

연속합 문제는 주어진 순열에서 연속적으로 선택한 값 중에서 최대를 구하는 문제입니다. 

 

예)

10 -4 3 1 5 6 -35 12 21 -1

다음 수열에서 최대는 12+21 = 33 입니다. 

 

리스트의 최대 길이는 10만이므로 for 문으로 구현하게 되면 시간 초과가 나옵니다. 따라서 동적 할당을 통해서 문제를 풀어야 합니다. 방법을 복잡하게 생각하기보다 단순하게 생각하는게 도움이 됩니다. 

 

수열 A가 주어질 때, 새로운 항 a를 A의 오른쪽에 붙인다면 세 가지 선택지가 주어집니다. 

 

1. 기존 A의 최대값을 선택한다. 

2. a 값을 새로운 최대값으로 설정한다. 

3.  기존 A의 최대값에 a를 더한다. 

 

이 세가지 경우에 대하여 동적으로 값을 저장하면서 수열을 확장하는 방식으로 구현하시면 됩니다. 

두 번의 실패 끝에 성공했습니다...ㅜㅜ 

# Input
N = int(input())
lst = list(map(int, input().split()))



# Input
N = int(input())
lst = list(map(int, input().split()))
 
#---------------------------------------------
# 1. 기존 최대    : 00000000000000000000000000
# 2. 새로운 최대  : 00000000000000000000000000
# 3. 두 개를 더함 : 00000000000000000000000000
#--------------------------------------------
mem = [[0 for i in range(3)] for j in range(N)] 
mem[0] = [lst[0] for i in range(3)]
 
#  Bottom Up Approach Construction
for i in range(1, N):
    mem[i][0] = max(mem[i-1])
    mem[i][1] = lst[i]
    mem[i][2] = max(mem[i-1][1], mem[i-1][2]) + lst[i]
 
# Result
print(max(mem[N-1]))