[Swift 알고리즘] LeetCode 53. Maximum Subarray

×

Dynamic Programming, Divide and Conquer | Medium

LeetCode 53. Maximum Subarray

 

for문 중첩해서 돌려서 O(n^2) 으로 풀었더니 당연히 시간초과 뜸,, Time Limit Exceeded

subarray 하나씩 더해가면서 값 저장하는 방식,, 

let solution = Solution()
print(solution.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) //6
print(solution.maxSubArray([-2])) //-2
print(solution.maxSubArray([1])) //1

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.max() ?? 0 < 0 { return nums.max() ?? 0 }
        var result = 0
        for i in 0..<nums.count {
            if nums[i] < 0 { continue }
            var sumArr = [0]
            for j in i..<nums.count {
                if sumArr.last! + nums[j] >= sumArr.last! {
                    sumArr[sumArr.count - 1] += nums[j]
                } else {
                    sumArr.append(sumArr.last! + nums[j])
                }
            }

            if let max = sumArr.max(), result < max {
                result = max
            }
        }
        return result
    }
}

 

모범 답안

이렇게나 간단하게 풀 수 있는 거였군요 ㅎㅎㅎ

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var sum = 0
        var result = nums[0]

        for num in nums {
            sum = max(num, sum + num)
            result = max(result, sum)
        }

        return result
    }
}