[LeetCode] Maximum Subarray

 

문제

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

 

예시

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.

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

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

---

풀기

우선 난 못풀었다(..)

내가 생각한 방법이 브루트 포스였으나 최적화를 고려하면 틀린 답인것 같아 치워버렸다.

gpt에게 물어본 역시 결과 브루트포스는 추천하지 않았다.

gpt는 카데인 알고리즘을 사용하라고 했고 함 찾아봄.

 

출처는 gpt..

 

카데인 알고리즘의 핵심 개념은 다음과 같다.

• 현재까지의 최댓값(currentSum)을 유지하면서 진행
• 이전 값 (currentSum + nums[i])과 현재 값 (nums[i])을 비교해 최댓값을 유지
• 한 번의 순회만으로 최댓값 구할 수 있음

 

따라서 점화식은 아래와 같다.

currentSum = max(nums[i], currentSum + nums[i])
maxSum = max(maxSum, currentSum)

// init
currentSum = nums[0]
maxSum = nums[0]

 

위 내용을 가지고 LeetCode에서 제시하는 예시 1번을 봐보자.

i	nums[i]	currentSum	maxSum
0	-2	max(-2, -2) = -2	max(-2, -2) = -2
1	1	max(1, -1) = 1	max(-2, 1) = 1
2	-3	max(-3, -2) = -2	max(1, -2) = 1
3	4	max(4, 2) = 4	max(1, 4) = 4
4	-1	max(-1, 3) = 3	max(4, 3) = 4
5	2	max(2, 5) = 5	max(4, 5) = 5
6	1	max(1, 6) = 6	max(5, 6) = 6
7	-5	max(-5, 1) = 1	max(6, 1) = 6
8	4	max(4, 5) = 5	max(6, 5) = 6

 

 

maxSum의 값을 보면 최대 부분 배열의 합은 6이고 [4, -1, 2, 1]이 그 부분 배열에 해당된다.

---

결과

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var currentSum = nums[0]
        var maxSum = nums[0]

        for (i in 1 until nums.size) {
            currentSum = maxOf(nums[i], currentSum + nums[i])
            maxSum = maxOf(maxSum, currentSum)
        }

        return maxSum
    }
}

위와 같다.

 

사실 잘 이해가 안갔는데 gpt한테 최대 합의 결과값 말고 그 부분 배열을 출력하도록 만들어달라고 해서 이해했다.

fun maxSubArrayWithIndices(nums: IntArray): Pair<Int, IntArray> {
    var currentSum = nums[0]
    var maxSum = nums[0]

    var startIndex = 0 // 현재 부분 배열의 시작점
    var tempStart = 0 // 새롭게 시작할 임시 인덱스
    var endIndex = 0 // 최대 부분 배열의 끝점

    for (i in 1 until nums.size) {
        if (nums[i] > currentSum + nums[i]) {
            currentSum = nums[i]
            tempStart = i // 새로운 subarray 시작점 설정
        } else {
            currentSum += nums[i]
        }

        if (currentSum > maxSum) {
            maxSum = currentSum
            startIndex = tempStart // 최대 부분 배열의 시작점 업데이트
            endIndex = i // 최대 부분 배열의 끝점 업데이트
        }
    }

    // 최대 부분 배열 추출
    val maxSubarray = nums.sliceArray(startIndex..endIndex)

    return Pair(maxSum, maxSubarray)
}

이게 내 질문에 gpt가 해준 대답.