[LeetCode] 53. Maximum Subarray

문제

leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

 

잠깐

우리가 같이 풀었던 로직을 활용해야 하는 로직입니다. 

저는 2가지 방식으로 풀었습니다.

 

코드 (22년 2월 15일 풀이)

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var maxSum = nums[0]
        var sumValue = nums[0]
    
        for index in 1..<nums.count {
            if sumValue < 0 {	//sumValue + nums[index] < nums[index]을 정리했습니다.
                sumValue = nums[index]
            } else {
                sumValue = sumValue + nums[index]
            }
        
            maxSum = max(maxSum, sumValue)
        }
        return maxSum
    }
}

 

설명

일반적으로 수를 더해갈땐 값이 증가합니다.

하지만 더할수록 값이 작아지는 경우가 있어요.

바로 음수 입니다!

음수인 a와 c, 양수인 b가 있다고 생각하세요.

다음과 같이 음수는 어떤 값이 더하더라도 값이 작아지죠.

a(음수) + b(양수) < b(양수)

a(음수) + c(음수) < c(음수)

 

그래서 값을 더해가다가 sum 값이 음수가 되면, 양수 혹은 음수인 다음 값을 아무리 더해도 값은 작아집니다.

따라서 sum 값이 음수가 되면, sub어레이 계산은 종료된겁니다. 아무리 더해도 값이 작아지니, 의미가 없잖아요.

그래서 다음 값을 sum으로 설정하여, 덧셈을 다시 시작합니다.

 

 

---------------------------------------------------------------------------------------------------------

 

코드 (21년 3월 20일 풀이)

최초 구현한 코드

class Solution {

    func maxSubArray(_ nums: [Int]) -> Int {
        var sums: [Int] = [Int](repeating: 0, count: nums.count+1)
        sums[0] = 0
        
        for i in 0..<sums.count-1 {
            sums[i+1] = sums[i] + nums[i]
        }

        var maxResult = Int.min
        var minValue = sums[0]

        for i in 1..<sums.count {
            if maxResult < nums[i-1] {
                maxResult = nums[i-1]
            }

            var currValue = sums[i]
            
            if currValue < minValue {
                minValue = currValue
            } else {
                var result = currValue - minValue
                if maxResult < result {
                    maxResult = result
                }
            }
        }
        return maxResult        
    }
}

 

메모리를 더욱 더 다듬은 코드

class Solution {

    func maxSubArray(_ nums: [Int]) -> Int {
        var maxResult = Int.min
        var sumValue = 0
        var minValue = 0

        for i in 0..<nums.count {
            if maxResult < nums[i] {
                maxResult = nums[i]
            }
            
            sumValue += nums[i]
            
            if sumValue < minValue {
                minValue = sumValue
            } else {
                var result = sumValue - minValue
                if maxResult < result {
                    maxResult = result
                }
            }
        }
        return maxResult        
    }
}

 

설명

연속된 숫자 합의 최대값 구하기입니다.

어디서 본 것 같은 느낌이죠????

바로 121번 문제와 완전 유사합니다. (심지어 코드도 유사해요)

 

121. Best Time to Buy and Sell Stock - skillist.tistory.com/213

121. Best Time to Buy and Sell Stock

이미 121번 문제를 통과한 상태인데도, 이번 문제를 풀면서 121번이 조금도 생각나지 않았다?????

더더욱 화이팅하고 노력해야 합니다. 코드, 설명 보지말고 121번 문제 다시 풀고 오세요.

 

sums 배열이 보이죠?

sums[0] = 0이며, sums[i+1] = sums[i] + nums[i] 입니다.

이렇게 합을 구해놓고, 121번 문제 풀듯이 차이의 값이 최대값인 경우를 구하면 됩니다.

단, 문제가 있습니다.

[-1] 배열인 경우 Int.min의 값을 출력합니다. 

뭐가 문제일까요?

생각해보면, 자기 자신 또한, 최대값이 될수 있기 때문에, 최대값과 nums[k]값을 비교해줘야 합니다.

 

또한, sums[0] = 0으로 설정했기 때문에, sums[0] ~ sums[nums.count]까지 비교 한다면, 실제 값이 아닌 0이 답으로 출력되는 경우가 있어 범위를 조심해야해요

[-2, -1]인 경우 sums[0]번부터 수행해볼까요?

(-3) - (-2) = (-1)이 수행되지만, minValue가 0이며, 0이 더 크기 때문에 잘못된 값이 출력됩니다.

보여드린 2가지 코드 중 "메모리를 더 다듬은 코드"를 통해 var sums: [Int] = [Int](repeating: 0, count: nums.count+1) 만큼의 메모리를 세이브할 수 있었습니다.

 

회고

 

제가 여러분에게 하고싶은 말은(저도 잘하는 편은 아니지만), 문제를 풀때는, 코드부터 작성하지 말고, 머릿속으로 로직을 생각하세요.

머리만으로 생각하기 어려우면, 노트에 펜을 끄적이면서 규칙을 찾아보세요.

실제로 DP(다이나믹 프로그래밍) 문제를 풀 때는, 노트에 끄적이며 규칙을 찾고, 구현해야합니다.

제가 작성한 알고리즘 공부 방법이 있으니 한번 읽어보세요

알고리즘 공부의 핵심은 "생각하는 힘!"입니다.

 

skillist.tistory.com/211

Leet Code 추천 75문제와 알고리즘 공부 방법