iOS Interview - Leetcode 53. Maximum Subarray

July 08, 20241 min read#swift, #interview, #leetcode

Leetcode: 53. Maximum Subarray

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

Further reading

Quick Drop logo

Profile picture

Personal blog by An Tran. I'm focusing on creating useful apps.
#Swift #Kotlin #Mobile #MachineLearning #Minimalist


© An Tran - 2024