53. Maximum Subarray; 152. Maximum Product Subarray

E53MaximumSubArray.java

public class E53MaximumSubArray {

     public int optimizedBruteForce(int[] nums) {
         var max = Integer.MIN_VALUE;
         for (var i = 0; i < nums.length; i++) {
             var current = 0;
             for (var j = i; j < nums.length; j++) {
                 current += nums[j];
                 max = Math.max(max, current);
             }
         }
         return max;
     }

     public int dynamicProgramming(int[] nums) {
         var bestSum = Integer.MIN_VALUE;
         var current = 0;
         for (var i : nums) {
             current = Math.max(i, current + i);
             bestSum = Math.max(bestSum, current);
         }
         return bestSum;
     }
 }

M152MaximumProductSubArray.java

public class M152MaximumProductSubArray {

    public int dynamicProgramming(int[] nums) {
        int result = nums[0];
        int currentMax = nums[0];
        int currentMin = nums[0];
        for (var i = 1; i < nums.length; i++) {
            int current = nums[i];
            int tempMax = Math.max(current, Math.max(current * currentMax, current * currentMin));
            currentMin = Math.min(current, Math.min(current * currentMax, current * currentMin));
            currentMax = tempMax;
            result = Math.max(result, currentMax);
        }
        return result;
    }
}