[백준/BOJ] 1912번: 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

해설

다른 방법들도 있지만 나는 분할 정복을 이용해서 문제를 해결하였다.

분할 정복이란 더 작은 문제들로 분할하여 문제를 해결해나가는 것이다.

 

인덱스의 최소값을 start, 최대값을 end, 중간값을 mid라고 하자.

이 때 최대 합이 있을 수 있는 구간은

1. [start ~ mid]에 최대 합이 있는 경우

2. [mid+1 ~ end]의 최대 합이 있는 경우

3. 최대 합이 중간에 걸쳐있는 경우

 

따라서 배열을 분할하여 위의 세가지 경우에서 만들어지는 값 중 최대값을 선택해가면

원하는 값을 얻을 수 있다.

소스 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = IntArray(n)
    val st = StringTokenizer(readLine())
    for(i in 0 until n) arr[i] = st.nextToken().toInt()
    println(divideConquer(arr, 0, n-1))
}
fun divideConquer(arr: IntArray, start: Int, end: Int): Int {
    if(start == end) return arr[start]
    val mid = (start + end) / 2
    var left = Int.MIN_VALUE
    var right = Int.MIN_VALUE
    var sum = 0
    for(i in mid downTo start) {
        sum += arr[i]
        left = maxOf(left, sum)
    }
    sum = 0
    for(i in mid + 1 .. end) {
        sum += arr[i]
        right = maxOf(right, sum)
    }
    val side = maxOf(divideConquer(arr, start, mid), divideConquer(arr, mid+1, end))
    return maxOf(left + right, side)
}