[HackerRank] The Maximum Subarray

def maxSubarray(arr):
    # Write your code here
    len_arr = len(arr)
    
    dp_array = [0]*(len_arr)
    dp_sequence = [0]*(len_arr)
    
    dp_array[0], dp_sequence[0] = arr[0], arr[0]
    
    for i in range(1,len_arr):
        dp_array[i] = max(arr[i], arr[i]+dp_array[i-1])
        
    for i in range(1,len_arr):
        dp_sequence[i] = max(dp_sequence[i-1], dp_sequence[i-1]+arr[i], arr[i])
        
    return [max(dp_array),dp_sequence[len_arr-1]]

이번 문제는 주어진 배열(arr)의 값들을 포함한 부분 배열(Sub array)와 부분 수열(Sub sequence) 중에서 그 합이 최대가 되는 값을 각각 구하는 문제이다.

 

문제를 풀기에 앞서 이 문제의 핵심은 1차원 DP 테이블을 선언하고 첫번째 원소부터 차근차근 DP 테이블에 최적 값을 저장해가며 푸는 'DP 알고리즘' 문제라는 것이다. 

 

처음에 이 문제를 접했을 때 부분 수열을 구하는 방법은 쉽게 떠올릴 수 있었는데, 연속적이지 않은 부분 수열은 단순하게 첫번째 원소를 초기 값으로 설정한 후에 두번째 원소부터 '이전까지의 최적 값(dp_sequence[i-1])', '이전까지의 최적 값 + 현재 원소 값(arr[i])', '현재 원소 값' 총 3가지를 비교하여 가장 큰 값을 저장해주면 된다.

 

그 다음으로 부분 배열의 경우에는 연속적으로 이루어져야 하므로 두번째 원소부터 '현재 원소를 이어붙이는 경우(dp_array[i-1] + arr[i])'와 '이어붙이지 않는 경우, 즉 연속적으로 배열을 이루었을 때 값이 더 작아지는 경우(arr[i])'를 각각의 원소에 저장해준다.

 

그리고 마지막으로 부분 수열의 경우에는 최적의 값들을 차근차근 저장(누적)해가며 풀었기 때문에 DP 테이블의 마지막 원소가 곧 답이 되고, 부분 배열의 경우에는 연속적이기 때문에 DP 테이블의 각 원소가 곧 최적값이기 때문에 해당 DP 테이블의 최댓값이 곧 답이 된다.

 

DP 알고리즘을 사용할 때, 가장 큰 문제를 해결하기 위해 작은 문제에서부터 차근차근 최적값을 저장해가는 것도 중요하지만 최적값을 유지하기 위한 조건 또한 매우 중요하다는 것을 배울 수 있었던 문제였다 :)