https://leetcode.com/problems/maximum-subarray/submissions/1659112629/

maximum Sum Subarray ****

TC =O(N)

public class KadaneAlgorithm {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0]; // Start with the first element
        int maxSum = nums[0];     // Initialize maxSum with the first element

        // Traverse the array from the second element
        for (int i = 1; i < nums.length; i++) {
            // If currentSum is negative, reset to current element
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            // Update maxSum if currentSum is greater
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }    
}

image.png

max product subarray

TC =O(N)

SC = O(1)

class Solution {
    public int maxProduct(int[] nums) {
        int currentMax = nums[0];
         int currentMin = nums[0];
        int maxProd =nums[0];

        for(int i = 1 ; i< nums.length; i++){

            int temp = currentMax;
            currentMax = Math.max(nums[i], Math.max(currentMin*nums[i] , currentMax*nums[i]));
            currentMin = Math.min(nums[i], Math.min(temp*nums[i] , currentMin*nums[i]));
            maxProd =  Math.max(currentMax ,maxProd);
        }
        return maxProd ;
    }
}