/* Given an array that contains both positive and negative integers, find
* the product of the maximum product subarray. Expected Time complexity is
* O(n) and only O(1) extra space can be used.
* http://www.geeksforgeeks.org/maximum-product-subarray/
*/
import java.io.*;
import java.util.*;
public class MaxProductSubarray {
public static void main(String[] args) {
//int[] arr = {6, -3, -10, 0, 2};
//int[] arr = {-1, -3, -10, 0, 60};
int[] arr = {-2, -3, 0, -2, -40};
solve(arr);
}
public static void solve(int[] arr) {
int prod = 1;
int max = Integer.MIN_VALUE;
int last_neg_prod = 0;
for(int i=0; i