[LeetCode/Kotlin]Medium - 53. Maximum Subarray

Maximum Subarray - LeetCode

문제

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

• 1 <= nums.length <= 105
• 104 <= nums[i] <= 104

풀이

나의 풀이법

풀이 접근 과정

처음엔 누적합에서 부분합을 구하는 방식으로 하였다.

그러나 그 로직에선 한가지 문제가 있다.

바로 최소값이 최대값보다 뒤에 오면 유효하지 않은 최솟값이 되는 것이다.

결국 누적합은 버리는 코드가 되었고, 다시 자세히 문제를 분석한 결과 아래와 같은 코드가 나왔다.

최종 소스코드

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var max = Int.MAX_VALUE * -1
        var sum = 0

        nums.forEach { 
            sum = maxOf(it, sum + it)
            max = maxOf(max, sum)
        }

        return max
    }
}