View on NeetCode
View on LeetCode

Problem

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.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Solution

Approach 1: Kadane’s Algorithm (Greedy)

The key insight is to maintain a running sum, and if it becomes negative, reset it to 0 (start a new subarray).

Implementation

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = 0

        for num in nums:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)

        return max_sum

Approach 2: Kadane’s (Alternative)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        current_sum = 0

        for num in nums:
            current_sum += num
            max_sum = max(max_sum, current_sum)

            # Reset if sum becomes negative
            if current_sum < 0:
                current_sum = 0

        return max_sum

Approach 3: Divide and Conquer

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def maxCrossingSum(nums, left, mid, right):
            # Max sum in left half ending at mid
            left_sum = float('-inf')
            curr_sum = 0
            for i in range(mid, left - 1, -1):
                curr_sum += nums[i]
                left_sum = max(left_sum, curr_sum)

            # Max sum in right half starting from mid+1
            right_sum = float('-inf')
            curr_sum = 0
            for i in range(mid + 1, right + 1):
                curr_sum += nums[i]
                right_sum = max(right_sum, curr_sum)

            return left_sum + right_sum

        def maxSubArrayHelper(nums, left, right):
            if left == right:
                return nums[left]

            mid = (left + right) // 2

            left_max = maxSubArrayHelper(nums, left, mid)
            right_max = maxSubArrayHelper(nums, mid + 1, right)
            cross_max = maxCrossingSum(nums, left, mid, right)

            return max(left_max, right_max, cross_max)

        return maxSubArrayHelper(nums, 0, len(nums) - 1)

Complexity Analysis

Kadane’s Algorithm:

• Time Complexity: O(n), single pass through array.
• Space Complexity: O(1), constant extra space.

Divide and Conquer:

• Time Complexity: O(n log n), similar to merge sort.
• Space Complexity: O(log n) for recursion stack.

Key Insights

1. Kadane’s Algorithm: Classic greedy approach for maximum subarray problem.

2. Greedy Choice: At each position, decide whether to extend current subarray or start a new one.

3. Local vs Global: Track both current subarray sum (local) and overall maximum (global).

4. Reset on Negative: If current sum becomes negative, it won’t help future subarrays, so reset to 0.

5. Alternative View: current_sum = max(num, current_sum + num) - either start fresh at num or extend current subarray.

6. Always Include Element: At each step, we must include the current element in some decision.