LeetCode #53: Maximum Subarray

LeetCode Solutions

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

The problem requires finding the maximum sum of a contiguous subarray. This problem can be solved using the Kadane’s algorithm, which is based on dynamic programming. We will maintain two variables max_so_far and max_ends_here that represent the maximum sum found so far and the maximum sum that ends at the current position, respectively.

  1. Initialize max_so_far and max_ends_here to the first element of the array.
  2. Loop through the array from the second element.
  3. Add the current element to max_ends_here.
  4. If max_ends_here is greater than max_so_far, update max_so_far.
  5. If max_ends_here is less than 0, reset it to 0.
  6. Return max_so_far

The solution uses a for loop to loop through the array and update the maximum sum found so far and the maximum sum that ends at the current position. The time complexity of the algorithm is O(n) since it loops through the array only once. The space complexity is O(1) since it uses only two variables to store the maximum sum found so far and the maximum sum that ends at the current position.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_so_far = nums[0]
        max_ends_here = 0
        
        for i in range(len(nums)):
            max_ends_here += nums[i]
            max_so_far = max(max_so_far, max_ends_here)
            if max_ends_here < 0:
                max_ends_here = 0
    
        return max_so_far

Time and Space Complexity

The Kadane’s algorithm is an efficient way of solving the maximum subarray problem. It is based on dynamic programming and has a time complexity of O(n) and space complexity of O(1).