15. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum. A subarray is a contiguous non-empty sequence of elements within an array.

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.

Input: nums = [1]
Output: 1

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

Problem Breakdown:

1. We use Kadane's Algorithm. Maintain a running sum (currentSum) and a maximum sum (maxSum). Initialize maxSum to the first element.

• maxSum = nums[0]
  currentSum = 0

2. Iterate through each number. If currentSum is negative, reset it to 0 because a negative prefix would only decrease future sums.

• for num in nums:
      if currentSum < 0:
          currentSum = 0

3. Add the current number to our running sum, extending the current subarray.

•     currentSum += num

4. Update maxSum if the current running sum exceeds the previous maximum.

•     maxSum = max(maxSum, currentSum)

5. After processing all elements, maxSum contains the largest subarray sum.

• return maxSum

Summary:

Kadane's Algorithm maintains a running sum. At each step, if the running sum is negative, discard it (reset to 0) because starting fresh is better. Track the maximum sum seen during iteration.

Time and Space Complexity:

Time Complexity: O(n) - single pass through the array.

Space Complexity: O(1) - only two variables used.

Python Solution:

def maxSubArray(nums):
    maxSum = nums[0]
    currentSum = 0
    for num in nums:
        if currentSum < 0:
            currentSum = 0
        currentSum += num
        maxSum = max(maxSum, currentSum)
    return maxSum

JavaScript Solution:

var maxSubArray = function(nums) {
    let maxSum = nums[0];
    let currentSum = 0;
    for (const num of nums) {
        if (currentSum < 0) currentSum = 0;
        currentSum += num;
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
};

Java Solution:

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = 0;
        for (int num : nums) {
            if (currentSum < 0) currentSum = 0;
            currentSum += num;
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}