https://leetcode.com/problems/maximum-subarray/submissions/1659112629/
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;
}
}

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