정수 배열의 최대 부분합 (연습문제)

배열의 연속된 부분집합의 최대합

정수 배열이 주어질 때 배열내의 연속된 원소를 더한 부분합의 최대값을 구하는 문제이다. 구간이 아닌 최대값 자체를 구하면 되는 문제이다.

간단히 생각하면 0부터 1, 2, 3 … n 까지의 합 중 최대인 값, 그 다음은 1부터 2, 3, 4 .. n 까지의 값 중 최대인값 이렇게 비교해나갈 수 있는데 그러면 반복계산이 너무 많다. 따라서 DP를 이용한다.

  1. 0번 인덱스까지의 최대합은 0번 값 그 자체이다.
  2. i번 인덱스까지의 최대 부분합은, (i-1) 번 까지의 최대 부분합과 i번 값의 합이다. 이 때 이전인덱스까지의 최대부분합이 0보다 작으면 더하지 않는다.

이렇게 하면 되지롱


func maxSubsum(arr: [Int]) -> Int {
    var result = Array(count: arr.count, repeatedValue: 0)
    result[0] = arr[0]
    for i in 1..<arr.count {
        result[i] = (result[i-1] > 0 ? result[i-1] : 0) + arr[i]
    }
    return result.reduce(result[0], combine: max)
}

참고로 swift3에서는 Array(count:repeatedValue:)Array(repeating:count:)로 인자의 위치가 뒤집어 졌으니 참고.

동적계획법

동적 프로그래밍

동적 프로그래밍은 세부 계산으로 나뉘어지는 하나의 큰 문제를 세부 계산 결과를 미리 구해서 저장한 후 큰 계산의 결과를 빠르게 도출해내는 문제해결 기법이다.(이름과는 달리 프로그래밍 테크닉은 아니다.) 흔히 피보나치 수열을 계산할 때 memoization도 동적 프로그래밍의 범주로 볼 수 있다. 동적계획법 더보기