[Kotlin] 릿코드 53 Maximum Subarray

📘 문제

https://leetcode.com/problems/maximum-subarray/

💡풀이

배열의 최대 길이가 10^5이므로 이중포문으로 연속되는 배열의 최대 합을 구하는 건 무리가 있다. 그래서 분할 - 정복 기법을 사용해야한다.
첫번째 인덱스(low)와 마지막 인덱스(high)로 중간지점의 인덱스(mid)를 구한 뒤
mid에서 low까지의 최대 합, mid+1에서 high까지의 최대 합을 구하며 이를 비교하고,
재귀를 돌려 범위를 좁혀가며 최대 값을 구하면 된다.

💻 코드

import kotlin.math.max

private fun main() {
    println(maxSubArray(intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4)))
}

private fun maxSubArray(nums: IntArray): Int {
    if (nums.size == 1) return nums[0]
    var answer = dividedSum(nums, 0, nums.lastIndex)
    return answer
}

private fun dividedSum(nums: IntArray, low: Int, high: Int): Int {
    if (low == high) return nums[low]

    val mid = (low + high) / 2
    var answer = 0

    var sum = 0
    var leftSum = Int.MIN_VALUE
    for (i in mid downTo low) {
        sum += nums[i]
        leftSum = max(leftSum, sum)
    }
    sum = 0
    var rightSum = Int.MIN_VALUE
    for (i in mid+1 .. high) {
        sum += nums[i]
        rightSum = max(rightSum, sum)
    }
    answer = max(dividedSum(nums, low, mid), dividedSum(nums, mid + 1, high))
    answer = max(leftSum+rightSum, answer)
    return answer
}

결과