9. 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. The idea is to maintain a running sum (currentSum) and a maximum sum (maxSum). We initialize maxSum to the first element since we need at least one element.

• maxSum = nums[0]
  currentSum = 0

2. We iterate through each number in the array. Before adding the current number, we check if our running sum is negative. If it is, we reset it to 0 because a negative prefix would only decrease any future subarray sum.

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

3. We add the current number to our running sum. This extends our current subarray by one element.

•     currentSum += num

4. We update maxSum if the current running sum exceeds our previously recorded maximum. This captures the best subarray sum seen so far.

•     maxSum = max(maxSum, currentSum)

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

• return maxSum

Summary:

Kadane's Algorithm works by maintaining a running sum. At each step, if the running sum is negative, we discard it (reset to 0) because starting fresh from the current element is better. We track the maximum sum seen at any point during the iteration.

Time and Space Complexity:

Time Complexity: O(n) - we iterate through the array once.

Space Complexity: O(1) - we only use two variables regardless of input size.

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;
    }
}