[LeetCode] Maximum Subarray

https://leetcode.com/explore/featured/card/top-interview-questions-easy/97/dynamic-programming/566/

Explore - LeetCode

 

[Dynamic Programming]

주어진 배열에서 연속된 subarray를 추출하여 나올 수 있는 합의 최댓값을 구하는 문제이다. 

즉 "연속된" 이라는 조건 하에 여러 가지의 경우의 수들 중에서 합이 최대인 것을 찾으면 된다. 

 

Dynamic Programming에 속해있는 문제이기에 처음에는 작은 문제들로 부터 시작해보려 했으나, 이전에 풀었던 투 포인터가 생각나서 시도해봤다..!

 

https://leechamin.tistory.com/444?category=941567 

[프로그래머스] 보석 쇼핑

조금 다르긴 하지만 유사한 개념으로 다가가면 풀 수 있을 것 같았다. 

 

[Two Pointer]

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.count == 1 { return nums[0] }
        
        var i = 0
        var j = 1
        var best = nums[0]
        var idx = [Int]()
        
        while i < nums.count && j < nums.count {
            if nums[i...j].reduce(0,+) > nums[j] {
                var cur = max(nums[i...j].reduce(0,+), nums[j])
                if best < cur {
                    best = cur
                    idx = [i,j]
                }
                j += 1
            } else {
                best = max(best,nums[j])
                i = j
                j += 1
            }
            
        }
        return best
    }
}

 

두 개의 인덱스(i, j)를 두고 이동해가며 값을 계속 비교해나갔다. 

 

var nums = [-2,1,-3,4,-1,2,1,-5,4]

nums가 Input으로 들어온다면, -2 + 1과 1을 비교해서 좌변이 더 크면 저장 후 j만 한 칸 이동 시키고, 그렇지 않다면 다시 처음부터 본다는 생각으로 i를 j로 j는 1만큼 이동시켜줬다.(그대로 한 칸씩 이동시켜준 것) 

 

그렇게 반복하면서 best의 값을 갱신해준다. 갱신시마다 인덱스(시작, 끝)도 저장해준다. 

(사실 이 문제에서는 인덱스를 구하지 않아도 되는데... 혹여나 최댓값이 아닌 subarray를 반환하라는 문제도 종종 있어 풀이해보았다.)

2개 케이스는 실패... 타임 리밋..

하지만! 지금 풀이로는 몇몇 문제만 풀 수 있고 timeout이 된다... 문제 유형이 알맞지 않아서 그런지... 적합하지 않은 풀이다. 

"그냥 인덱스도 구해봤다"에 의미를 두어야 하나 싶다.

[Dynamic Programming]

 

이제 다시 문제가 원하는 대로 풀이를 해보자. 

Dynamic Programming은 문제를 쪼개서 풀어나간다고 생각하면 된다. 히스토리를 참고하여 계속 값을 갱신해나가는(?) 그런 형태라 생각하고 풀이했다. 

 

그래서 우선 각 첫 번째 값들을 저장하고 시작했다. 

 

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.count == 1 { return nums[0] }
        
        var cur = nums[0]
        var best = nums[0]
        
        for i in 1..<nums.count {
            cur = max(cur + nums[i], nums[i])
            best = max(best, cur)
        }
        return best
    }
}

 

아까보다 훨씬 간결한 코드를 볼 수 있다.

 

값을 비교하는 방식은 아까 봤던 풀이와 같다. (이전 값 + 현재 값)과 (현재 값)을 비교하여 현재 보고 있는 배열의 합을 구하고 그게 최대인지 기존의 최대값과 비교하여 저장하는 방식이다. 

 

기본적인 동적 프로그래밍인 것 같은데 아직 익숙하지 않은 듯 하다.. 기초 문제들을 더 풀어봐야 할 것 같다.

끄읕