[백준 1912번] 연속합

n = int(input())

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

if n == 1:
    print(array[0])

else:
    dp = [0]*n

    dp[0] = array[0]

    for i in range(1,n):
        dp[i] = max(array[i],dp[i-1] + array[i])

    print(max(dp))

이번 문제는 주어진 수열에서 연속된 수열 중 가장 합이 큰 수열의 합을 구하는 문제이다.

 

처음에는 어떻게 경우의 수를 구해야할지 고민했었는데 곰곰히 생각해보니 첫번째 수부터 연속된 수열을 찾는 경우, 결국에는 마지막 수까지 고려를 해야한다는 것을 깨닫고 DP 알고리즘을 사용하여 첫번째 수부터 시작해서 최적의 값을 DP 테이블에 저장해가는 방식으로 풀어보기로 했다.

 

각 자리마다 이전까지의 최대 값과 해당 자리의 값을 더했을 때, 최대가 되도록 해야 하기 때문에 dp[i] = max(array[i],dp[i-1] + array[i])로 DP 테이블에 값을 저장해 나갔다.

 

몇일 전까지만 해도 풀지도, 감이 오지도 않았던 문제였는데 DP알고리즘이 '한번 계산한 문제에 대해서는 다시 계산하지 않도록 최적의 값을 기억, 즉 별도의 자료구조에 저장하면서 푸는 알고리즘'라는 점을 떠올리면서 쉽게 풀이할 수 있었던 문제였다 :)