53. Maximum Subarray

[lenaios]

https://leetcode.com/problems/maximum-subarray

[lenaios]

https://gist.github.com/lenaios/834ae9050a0b3272355dbfdea828396e

[zekexros]

https://github.com/zeke-iOS/AlgorithmPractice/blob/main/LeetCode/Leet-53.swift

[ghis22130]

흐ㅁ.. 시간 초과..

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.count == 1 { return nums[0] }

        var dp: [[Int]] = Array(repeating: [], count: nums.endIndex)

        dp.enumerated().forEach {
            dp[$0.0].append(nums[$0.0])
        }

        for i in 0..<nums.endIndex {
            for j in i+1..<nums.endIndex {
                dp[i].append(dp[i][j-i-1] + nums[j])
            }
        }

        return dp.compactMap{ $0.max() }.max()!
    }

}