53.Maximum_Subarray_(Medium).md

53. Maximum Subarray (Medium)

Date and Time: Jun 25, 2024, 12:54 (EST)

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

Question:

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6

Explanation: The subarray [4, -1, 2, 1] has the largest sum 6.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5, 4, -1, 7, 8]

Output: 23

Explanation: The subarray [5, 4, -1, 7, 8] has the largest sum 23.

KeyPoints:

This is the Kadane's Algorithm: 1. The subarray with negative sum is discarded (by assigning max_ending_here = 0 in code). 2. We carry subarray till it gives positive sum.

We use curSum to keep track of current sum, if curSum < 0 we reset it to0 because when nums = [-1, -2] or nums = [-2, 1, -3], after we reintialize curSum = 0 we add i into curSum then we compare maxSum = max(maxSum, curSum), so if i is the maximum number in nums, it will be store into maxSum, otherwise, if curSum >= 0 we will continue add i into curSum and compare max(maxSum, curSum).

My Solution:

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

Time Complexity: $O(n)$ because we only loop over the array.
Space Complexity: $O(1)$