Swift) LeetCode(Easy) - Maximum Subarray(DP)

leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

안녕하세요. 후르륵짭짭 입니다

오늘도 DP문제는 항상 잘 못 풉니다...

아이디어를 생각하기 쉽지 않아서요....

그래서 결국 도움을 받았고 그 알고리즘을 저만의 풀이로 풀었습니다.

func maxSubArray(_ nums: [Int]) -> Int {

    var maxSingle = nums[0]
    var currentNum = 0
    var maxNum : Int? = nil
    
    for item in nums{
    
        currentNum += item
        
        if maxNum == nil {
            maxNum = currentNum
        }
        else{
            maxNum = max(maxNum! , currentNum)
        }
        
        if currentNum < 0 {
            currentNum = 0
        }
        
        
    }
    
    return maxNum ?? maxSingle
}

완성된 코드는 이렇습니다.

www.youtube.com/watch?v=5WZl3MMT0Eg&t=403s

이 분의 도움을 받았고요.

설명은 그대로 입니다.

 

저는 무조건 모든 경우에 대해서 계산하려 했습니다.

그런데 음수일 경우에는 요소 중 가장 작은 값이 정답일 거입니다.

따라서 maxSingleNum을 모든 요소를 탐색하면서 가장 큰 값으로 갱신해줍니다.

 

그렇다면 음수가 나와서 음수가 되면 current 값을 0으로 만들어주고

다시 처음 부터 올라가도록 합니다.

그리고 가장 큰 값을 max 함수를 통해 찾아 줍니다.

 

Easy인데,,,, DP 문제는 어렵습니다.

프로그래머스와 LeetCode를 번갈아 가면서 풀면 큰 도움이 될 것 같습니다.

모두 즐코 하세요 ㅠㅠ