iOS Interview - Leetcode 53. Maximum Subarray

July 08, 2024 • 1 min read • #swift, #interview, #leetcode

Solution

Primary idea: Dynamic Programming, each element should be either with previous sequence or start a new sequence as the maximum one (Kadane’s Algorithm)
Time Complexity: O(n)
Space Complexity: O(1)

func maxSubArray(_ nums: [Int]) -> Int {
    var max_so_far = Int.min
    var max_ending_here = 0
    
    for num in nums {
        max_ending_here = max_ending_here + num
        max_so_far = max(max_so_far, max_ending_here)
        if max_ending_here < 0 {
            max_ending_here = 0
        }
    }
    
    return max_so_far
}

print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) // 6
print(maxSubArray([1])) // 1
print(maxSubArray([5,4,-1,7,8])) // 23

Solution

Further reading