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

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

정수 배열이 주어질 때 배열내의 연속된 원소를 더한 부분합의 최대값을 구하는 문제이다. 구간이 아닌 최대값 자체를 구하면 되는 문제이다.
간단히 생각하면 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:)로 인자의 위치가 뒤집어 졌으니 참고.