Maximum SubArray

XXX.Maximum Subarray

Dynamic Programming

Greedy

Problem Statement:

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

Algorithm:

1. Initialize two variables:
   • currMax to track the sum of the current subarray.
   • max to track the global maximum subarray sum.
2. Iterate through the array:
   • Update currMax as the maximum between the current element and the sum of currMax + num.
   • Update max as the maximum of max and currMax.
3. Return max as the result.
4. Old Version: The same logic but initializes currMax and max using the first element to ensure the subarray has at least one element.

Complexity:

Time: O(n), where n is the length of the array, as we iterate through the array once. | Space: O(1), as only constant extra space is used.

Java Implementation:

class Solution {

    // Optimized Kadane's Algorithm
    public int maxSubArray(int[] nums) {
        int currMax = 0; // Tracks the current subarray sum
        int max = Integer.MIN_VALUE; // Tracks the maximum subarray sum

        // Iterate over all numbers
        for (int num : nums) {
            currMax = Math.max(currMax + num, num); // Update current max subarray sum
            max = Math.max(max, currMax);          // Update the global max
        }

        return max; // Return the maximum sum found
    }

    // Slightly different version of Kadane's Algorithm
    public int maxSubArrayOld(int[] nums) {
        int currMax = nums[0]; // Start with the first element
        int max = nums[0];     // Start with the first element as the maximum

        // Iterate from the second element
        for (int i = 1; i < nums.length; i++) {
            currMax = Math.max(nums[i], currMax + nums[i]); // Extend or start a new subarray
            max = Math.max(max, currMax);                  // Update the global max
        }

        return max; // Return the maximum sum found
    }
}