Popular Posts

Saturday, July 30, 2011

Maximum contiguous product in an Array

Given an array of natural numbers (+ve, 0, -ve) find the maximum product of continuous elements.


input  : a = { 11, 4, 5, -2, 0, -3, -4, 4, 2, 3, 5, -7 };
output : 3360(From index positions 7 to 12)


class MaximumContiguousProduct {

public static void main(String[] args) {
int[] a = { 11, 4, 5, -2, 0, -3, -4, 4, 2, 3, 5, -7 };
int product = getMaximumProduct(a);
System.out.println(product);
}

/**
* Track zero positions and calculate maximum product till zero
*
* @param a
* @return
*/
public static int getMaximumProduct(int[] a) {

if (a == null || a.length == 0)
return 0;

int start = 0;
int maxSubArrayProduct = 0;
int maxProduct = -3421545;
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {// if ith element is zero then send i-1 element as
// end position
maxSubArrayProduct = getMaxProductInSubArray(a, start, i - 1);
start = i + 1;// skip the ith element.
} else if (i == a.length - 1) {
maxSubArrayProduct = getMaxProductInSubArray(a, start,
a.length - 1);
}
if (maxSubArrayProduct > maxProduct)
maxProduct = maxSubArrayProduct;
}
return maxProduct;
}

// in this sub array check if array contains even number of -ve numbers or
// odd.
// If it is even number,max product is product of all numbers
// else we will get two products.
private static int getMaxProductInSubArray(int[] a, int start, int end) {

if (a == null || a.length == 0 || start > end)
return 0;
else if (start == end)
return a[start];

int numberOfNegativeNumbers = 0;
int totalProduct = 1;
for (int i = start; i <= end; i++) {
if (a[i] < 0)
numberOfNegativeNumbers++;
totalProduct = totalProduct * a[i];
}

if (numberOfNegativeNumbers % 2 == 0)// handling case for even number of
// negative numbers.
return totalProduct;

// for odd number of -ve numbers,total prod value is -ve.calculate prod1
// and prod2
int prod1 = 1;
int i = start;
while (a[i] > 0) {// calculating till we trace first -ve number
prod1 = prod1 * a[i];
i++;
}
int prodRem1 = totalProduct / (prod1 * a[i]);

int prod2 = 1;
i = end;
while (a[i] > 0) {// calculating till we trace first -ve number
prod2 = prod2 * a[i];
i--;
}

int prodRem2 = totalProduct / (prod2 * a[i]);

return prodRem1 > prodRem2 ? prodRem1 : prodRem2;
}
}

No comments:

Post a Comment