Maximum Subarray [Kadanes with Foreach Loop]

53.Maximum Subarray

Array

Dynamic Programming

Greedy

Divide and Conquer

Problem Statement:

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.

Example:

Input:

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

→

Output:

6

The subarray [4,-1,2,1] has the largest sum = 6

Algorithm:

1. Use Kadane's algorithm to track current and max sum
2. For each number, decide to extend or start new subarray
3. Update global maximum at each step
4. Handle both versions (starting at 0 or first element)

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

// Version starting with 0
public int maxSubArray(int[] nums) {
    int currMax = 0;            // Current subarray sum
    int max = Integer.MIN_VALUE; // Maximum sum found
    
    for (int num : nums) {
        // Either extend current subarray or start new one
        currMax = Math.max(currMax + num, num);
        max = Math.max(max, currMax);
    }
    
    return max;
}

// Version starting with first element
public int maxSubArrayOld(int[] nums) {
    int currMax = nums[0]; // Start with first element
    int max = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        // Either extend current subarray or start new one
        currMax = Math.max(nums[i], currMax + nums[i]);
        max = Math.max(max, currMax);
    }
    
    return max;
}

Python Solution:

def maxSubArray(self, nums: List[int]) -> int:
    curr_max = 0           # Current subarray sum
    max_sum = float('-inf') # Maximum sum found
    
    for num in nums:
        # Either extend current subarray or start new one
        curr_max = max(curr_max + num, num)
        max_sum = max(max_sum, curr_max)
    
    return max_sum

# Version starting with first element
def maxSubArrayOld(self, nums: List[int]) -> int:
    curr_max = max_sum = nums[0] # Start with first element
    
    for num in nums[1:]:
        # Either extend current subarray or start new one
        curr_max = max(num, curr_max + num)
        max_sum = max(max_sum, curr_max)
    
    return max_sum

C++ Solution:

int maxSubArray(vector<int>& nums) {
    int currMax = 0;     // Current subarray sum
    int maxSum = INT_MIN; // Maximum sum found
    
    for (int num : nums) {
        // Either extend current subarray or start new one
        currMax = max(currMax + num, num);
        maxSum = max(maxSum, currMax);
    }
    
    return maxSum;
}

// Version starting with first element
int maxSubArrayOld(vector<int>& nums) {
    int currMax = nums[0]; // Start with first element
    int maxSum = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        // Either extend current subarray or start new one
        currMax = max(nums[i], currMax + nums[i]);
        maxSum = max(maxSum, currMax);
    }
    
    return maxSum;
}