Maximum Product Subarray
This program finds maximum product subarray.
Problem Statement
Write a Java program to find maximum product subarray in an integer array.
Source Code
| 1 | public class MaxProductSubarray { |
| 2 | public static void main(String[] args) { |
| 3 | System.out.println("Eduinq Maximum Product Subarray"); |
| 4 | int[] arr = {2,3,-2,4}; |
| 5 | int max=arr[0], min=arr[0], result=arr[0]; |
| 6 | for(int i=1;i<arr.length;i++){ |
| 7 | if(arr[i]<0){ |
| 8 | int temp=max; max=min; min=temp; |
| 9 | } |
| 10 | max=Math.max(arr[i],max*arr[i]); |
| 11 | min=Math.min(arr[i],min*arr[i]); |
| 12 | result=Math.max(result,max); |
| 13 | } |
| 14 | System.out.println("Maximum product subarray = "+result); |
| 15 | } |
| 16 | } |
Program Output
Eduinq Maximum Product Subarray Maximum product subarray = 6
Explanation
Since negative numbers can flip the sign of a product, the roles of max and min are swapped whenever a negative element is seen, and both are updated each iteration while result tracks the overall maximum product found.