Maximum Subarray

Problem Statement:

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1: 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.

Example 2: Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.

Example 3: Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Solution:

1. Recursion and Memoization:

class Solution {
    public int maxSubArray(int[] nums) {
        // We use an array to keep track of the maximum sum found so far.
        int[] maxSum = new int[]{Integer.MIN_VALUE};
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);
        // Start the recursion from the last index.
        maxSubArrayUtil(nums, nums.length - 1, maxSum, memo);
        return maxSum[0];
    }
 
    private int maxSubArrayUtil(int[] nums, int idx, int[] maxSum, int[] memo) {
        // Base case: If idx is out of bounds, return 0 (end of recursion).
        if (idx < 0) {
            return 0;
        }
 
        if(memo[idx] != -1){
            return memo[idx];
        }
 
        // Recursive step: Get the maximum subarray sum ending at the previous index.
        int currentMax = maxSubArrayUtil(nums, idx - 1, maxSum, memo);
 
        // Include the current element to the previous subarray or start a new subarray with the current element.
        int sumIncludingCurrent = Math.max(nums[idx], currentMax + nums[idx]);
 
        // Update the global maximum sum if the current subarray sum is larger.
        maxSum[0] = Math.max(maxSum[0], sumIncludingCurrent);
 
        // Return the maximum sum ending at the current index.
        return memo[idx] = sumIncludingCurrent;
    }
}

2. Tabulation

class Solution {
    public int maxSubArray(int[] nums) {
        // We use an array to keep track of the maximum sum found so far.
        int n = nums.length;
        int[] dp = new int[n + 1];
        //base case
        dp[0] = nums[0];
        int maxSum = dp[0];
 
        for(int i = 1; i < n; i++){
            int currentMax = dp[i - 1];
            dp[i] = Math.max(nums[i], currentMax + nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

3. Space Optimized:

class Solution {
    public int maxSubArray(int[] nums) {
        // We use an array to keep track of the maximum sum found so far.
        int n = nums.length;
        
        int prev = nums[0];
        int maxSum = prev;
 
        for(int i = 1; i < n; i++){
            int curr = Math.max(nums[i], prev + nums[i]);
            maxSum = Math.max(maxSum, curr);
 
            prev = curr;
        }
        return maxSum;
    }
}