Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

  • Constraints:

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

  • Example:

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.

Solution

Approach: Kadane's Algorithm

Kadane's algorithm is a dynamic programming approach to solve this problem efficiently.

  • Core Idea: The maximum sum of a subarray ending at a particular position i is either nums[i] itself (starting a new subarray) or nums[i] added to the maximum sum of a subarray ending at i-1. We track this current_max.

  • Global Maximum: We also need to keep track of the global_max sum found across all subarrays processed so far.

  • Steps:

    1. Initialization: Initialize current_max and global_max with the first element of the array nums[0]. This handles cases where all numbers are negative correctly.
    2. Iteration: Iterate through the array starting from the second element (i = 1 to n-1):
      • For each element nums[i], update current_max: current_max = max(nums[i], current_max + nums[i]).
      • Update global_max: global_max = max(global_max, current_max).
    3. Result: After iterating through all elements, global_max will hold the largest subarray sum.
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        # According to constraints, nums.length >= 1, so nums[0] is always available.
        current_max = nums[0]
        global_max = nums[0]

        # Iterate from the second element
        for i in range(1, len(nums)):
            # The maximum sum ending at index i is either nums[i] itself 
            # (starting a new subarray) or nums[i] added to the maximum sum 
            # ending at i-1. We take the larger of these two.
            current_max = max(nums[i], current_max + nums[i])
            
            # The global maximum sum is the larger of the current global max
            # and the maximum sum ending at the current position.
            global_max = max(global_max, current_max)
            
        return global_max