Question

How to get maximum product of subarray in Java

Answer 1

public class MaxProductOfSubarray_Java {
    public static int getMaxProductOfSubarray(int[] arr) {
        int len = arr.length;
         
        if (len == 0) {
            return 0;
        }
 
        int max_current_index = arr[0], min_current_index  = arr[0], max_product = arr[0];
         
        System.out.format("arr[i] = %d max_current_index = %d  min_current_index = %d max_product = %d\n", arr[0], max_current_index, min_current_index, max_product);
  
        for (int i = 1; i < len; i++) {
            int temp = max_current_index;
  
            max_current_index = Integer.max(arr[i], Integer.max(arr[i] * max_current_index, arr[i] * min_current_index ));
  
            min_current_index = Integer.min(arr[i], Integer.min(arr[i] * temp, arr[i] * min_current_index ));
             
            System.out.format("arr[i] = %d max_current_index = %d  min_current_index = %d\n", arr[i], max_current_index, min_current_index);
  
            max_product = Integer.max(max_product, max_current_index);
             
            System.out.format("max_product = %d\n", max_product);
        }
  
        return max_product;
    }
    public static void main(String args[]) {
        int[] arr = { -4, 8, 2, 5, 90, 7, 0, -3, 6 }; // 8 * 2 * 5 * 90 * 7 = 50400
  
        System.out.print("maximum product = " + getMaxProductOfSubarray(arr));
    }
}
 
 
 
 
/*
run:
 
arr[i] = -4 max_current_index = -4  min_current_index = -4 max_product = -4
arr[i] = 8 max_current_index = 8  min_current_index = -32
max_product = 8
arr[i] = 2 max_current_index = 16  min_current_index = -64
max_product = 16
arr[i] = 5 max_current_index = 80  min_current_index = -320
max_product = 80
arr[i] = 90 max_current_index = 7200  min_current_index = -28800
max_product = 7200
arr[i] = 7 max_current_index = 50400  min_current_index = -201600
max_product = 50400
arr[i] = 0 max_current_index = 0  min_current_index = 0
max_product = 50400
arr[i] = -3 max_current_index = 0  min_current_index = -3
max_product = 50400
arr[i] = 6 max_current_index = 6  min_current_index = -18
max_product = 50400
maximum product = 50400
 
*/

 

70+ SQL courses for beginners and professionals