leetcode: 53. Maximum Subarray

문제링크

풀이1

• 메모이제이션
• dp[i] : i번째까지의 최대SubArray

import kotlin.math.max

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        val dp = Array<Int>(nums.size) { Int.MIN_VALUE }     
        dp[0] = nums[0]
         var maxValue = dp[0]
        for (i in 1 until nums.size) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
            maxValue = max(maxValue, dp[i])
        }
        return maxValue
    }
}

시간복잡도 : O(N)
공간복잡도 : O(N)

풀이2

• 분할과 정복
• mid = (start + end) / 2
• mid ~ start 까지의 최대 부분 배열 -> a
• mid + 1 ~ end 까지의 최대 부분 배열 -> b
• a, b 를 합친 값 -> c
• a, b, c 의 최대값을 계산

import kotlin.math.max

class Solution {
    private fun findMaxSubArray(nums: IntArray, start: Int, end: Int): Int {
        if (start == end) return nums[start]
        val mid = (start + end) / 2
        val maxLeftSubArray = findMaxSubArray(nums, start, mid)
        val maxRightSubArray = findMaxSubArray(nums, mid + 1, end)
        val maxMidCrossSubArray = findMaxMidCrossSubArray(nums, start, mid, end)
        return max(maxLeftSubArray, max(maxRightSubArray, maxMidCrossSubArray))
    }
    
    private fun findMaxMidCrossSubArray(nums: IntArray, start: Int, mid: Int, end: Int): Int {
        var sum = 0
        var maxLeft = Int.MIN_VALUE
        for (i in mid downTo(start)) {
            sum += nums[i]
            maxLeft = max(maxLeft, sum)
        }
        sum = 0
        var maxRight = Int.MIN_VALUE
        for (i in (mid + 1)..end) {
            sum += nums[i]
            maxRight = max(maxRight, sum)
        }
        return maxLeft + maxRight
    }
    
    fun maxSubArray(nums: IntArray): Int {
        return findMaxSubArray(nums, 0, nums.size - 1)
    }
}