CareerCup

Count the number of negatives in the array, at the same time check for any zeroes in the array.

If there is a zero in the array, get the max-product from the left and right sub-arrays and find the max of them.

If there are no zeroes :
1. if no. of negatives is even, max-product is the product of all numbers.
2. if it is odd, iterate the array in both forward and backward directions and compute the product until you discover a negative number. Now, ignore the side where the product's absolute value is lesser.
eg : [ -100, 2, 25, -1, 8, -5, 22]
no. of negatives are 3 here.
When you iterate the array from both directions : fwd-product is -100 and bwd-product is -110. So ignore the values in the forward direction. So the max-product is 44000

public static int findMaxProduct(int[] array, int begin, int end) {
		int noNegs = 0; // count of negative numbers in the array
		int zeroIndex = -1; // index where a '0' is present
		for ( int i = begin; i < end; ++i) {
			if (array[i] < 0) {
				++noNegs;
			}
			if (array[i] == 0) {
				zeroIndex = i;
			}
		}
		
		if (zeroIndex > 0) {
			int l = findMaxProduct(array, begin, zeroIndex);
			int r = findMaxProduct(array, zeroIndex+1, end);
			return Math.max(l, r);
		}
		
		if (noNegs % 2 == 0) {
			int product = 1;
			for (int i = begin; i < end; ++i) {
				product *= array[i];
			}
			return product;
		}
		
		int fi, bi; // forward and backward indices
		int fp = 1, bp = 1; // forward and backward products
		for (fi = begin; fi < end; ++fi) {
			fp *= array[fi];
			if (array[fi] < 0) {
				break;
			}
		}
		for(bi = end-1; bi >= begin; --bi) {
			bp *= array[bi];
			if (array[bi] < 0) {
				break;
			}
		}
		
		int product = 1;
		int pbegin = (fp>bp) ? fi+1 : begin;
		int pend = (fp>bp) ? end : bi;
		
		for (int i = pbegin; i < pend; ++i) {
			product *= array[i];
		}
		return product;
	}

This is a standard DP problem. Trick is to keep track of min and max of the subarray ending at i in the array indices 0 to i. While calculating the min or max, we also need to examine max or min respetively.
I'll post the code in a couple of hours.
Algorithm will be O(n)

You can see kadane's algorithm for the case of Sum. Product is just more refined problem, which uses the same algorithm.

Does the problem want a subarray or just sum of the subarray?

Thank YD for reminding. I misunderstood the question.
Here's an O(n) solution for max product (inspired by the "longest valid parentheses" problem):

static int product(int A[], int begin, int end)
{
	int i, step, mh, ma;

	step = begin>end?-1:1;

	ma = A[begin]; mh = 1;
	for (i = begin; i != end; i += step) {
		mh *= A[i];
		if (mh > ma)
			ma = mh;
		if (A[i] == 0)
			mh = 1;
	}

	return ma;
}

int max_subarray_product(int A[], int n)
{
	int x, y;
	x = product(A, 0, n-1);
	y = product(A, n-1, 0);
	return x>y?x:y;
}

#include <stdio.h>
#include <stdlib.h>



void main (void)
{
//int tab[10]={4,5,8,0,13,-3,4,15,-2,5};
int tab[10]={4,5,5,10,-1,7,100,2,0,2000000};
int i;
int mux=1;
int max=1;
int x=0;
int pos_x=0;
int pos_y=0;

for(i=0; i<10; i++)
{


mux= mux*tab[i];

if(mux > max){
max=mux;

pos_x=x;
pos_y=i;

}
else{


if(mux==0 || mux < 0){

mux=1;
x=i+1;}

}
}


printf(" pos_x=%d and pos_y=%d \n", pos_x,pos_y);

}

1) Call the original set S. Go through set S and remove all 0s, count the negative numbers, and mark the smallest negative number. Also note if a 0 was removed. Call this new set S'
2) if there is an even number of negative numbers return the product of S'
3) if there is an odd amount of negative numbers remove the smallest negative number from S' and return the product of S'. Corner case: if the size of S' is 1 and a zero was removed, return 0.

#include<iostream>

using namespace std;

int a[31]={15,3,-10,0,-20,23,25,2,-4,19,33,-39,41,-48,37,21,65,-73,69,28,46,-88,93,52,-56,44,98,-7,-9,-100,121};

int main()
{
    int min=0;
    int c=0,t;
    for(int i=0;i<31;i++)
    {
        if(a[i]<min)
            min=a[i];
    }
    int mul=1;
    for(int i=0;i<31;i++)
    {
        if(a[i]<0)
        {
            if(min<a[i])
            {
              min=a[i];
              t=i;
            }
            c++;
        }
    }
    //cout<<min<<"\n";
    if(c%2!=0)
        a[t]=0;
     for(int i=0;i<30;i++)
    {
        if(a[i]!=0)
        {
            mul*=a[i];
        }
    }
    cout<<mul;
}

We are looking for the maximum product of an array elements. It apparent that we should ignore zeros since considering zeros simplifies the problem to find the maximum product of sub-arrays that are between these zeros (if there is only one zero, the max product of its left values and right values). If this is an acceptable assumption, it is also apparent that the product of the entire array elements is the answer if there is no negative values. This is also true if there exists even number of negative values. Hence, we can check and see if there are even or odd number of negative values and find the required maximum product accordingly.

void MaxProductSubArray(int *a, int n)
{
	int cnt=0,i;
	int prod=1;
	int max=INT_MIN,I=INT_MIN;
	for(i=0;i<n;i++)
	{
		if(a[i]<0)
			cnt++;
		if(a[i]!=0)
			prod*=a[i];
	}
	if(cnt%2==0)
		printf("%d\n",prod);
	else
	{
		for(i=0;i<n;i++)
		{
			if(a[i]<0)
			{
				if(prod/a[i]>max)
				{
					max=prod/a[i];
					I=i;
					printf("---> %d\t%d\n",i,a[i]);
				}
			}
		}
		printf("\nMAX:\t%d\n",max);
	}
}

}

My code that passed Leetcode OJ:

Explanations in changhaz(dot)wordpress(dot)com

class Solution {
public:
int maxProduct(int A[], int n) {
if (n==0) return 0;

int maxi = 1, mini = 1;
int out = INT_MIN;

for (int i=0;i<n;i++) {
int oldmaxi = max(maxi,1);
if (A[i] > 0) {
maxi = oldmaxi*A[i];
mini *= A[i];
} else {
maxi = mini*A[i];
mini = oldmaxi*A[i];
}
out = max(out,maxi);
}

return out;
}
};

Take a logarithm of each number, at this point the problem reduces to largest sum of subarray problem, which can be easily solves with Kadane's algorithm.

If the interviewer insists on using integers, the problem can be solved with a modified Kadane's algorithm, which keeps track of the largest and smallest product.

For an array with both positive and negative numbers we can notice that:
1. zero is to be ignored unless the array contains exactly 2 numbers {-v, 0}
2. Positive numbers are always wanted
3. Negative numbers are wanted as long as there is an even number of them
and in this case you want the smallest ones so to create the largest positive
product of them.

Because of the mixture you have to start by sorting them o(nlogn)
once sorted you can find the answer in a single scan of the sorted array while:
1. keeping track of the number negative numbers - ignore the biggest (closest to zero) negative number if there is an odd number of negative numbers.
2. Ignore 0 if possible (only one case require the use of 0)
3. Once reaching at the positive numbers continue to calculate till the end.

for(i=0;i<n;i++)
	{
		if(a[i]!=0)
		{
		if(currValue*a[i]>curValue)
			maxProd=(curValue*a[i]>maxProd?currValue*a[i]:maxProd);		
		curValue=curValue*a[i];
		}
	}
	return max;

An O(n) solution:

int max_subarray(int A[], int n)
{
	int i, mh, ma;
	mh = ma = A[0];
	for (i = 1; i < n; i++) {
		mh += A[i];
		if (mh < A[i])
			mh = A[i];
		if (mh > ma)
			ma = mh;
	}
	return ma;
}

This question is not making much sense.

A. If all the elements are positive, the whole array would be the largest contiguous subarray whose product is maximum

B. If the elements are non-negative, we will have to find the maximum of product of subarrays delimited by 0s

C. If the elements can contain -ve numbers, +ve numbers along with zeroes, the maximum product of a subarray is obtained as follows;
0. Set begin = 0
1. From 'begin' traverse the array until you find a 0 and demarcate it as 'end'.
2. Between begin and end, take the count, c of the number of -ve numbers and note the 'first'and 'last' positions of -ve numbers.
2a. If the c is even, multiply all the numbers between begin and (end-1) and take the product
2b. If the c is odd, take 2 products - one of the contiguous subarray between the 'begin' and the (last-1) and the other of the contiguous subarray between (first+1) and (end-1) and take the maximum of the two.
3. If the current running product is greater than the maximum global contiguous subarray product, update the global contiguous subarray product
4. if end<size_of_the_array, move 'begin' to the next non-zero element to it's right and goto step 1. else stop

void MaxProductSubArray(double *a, int n)
{
	try
	{
		if(a==NULL || n<=0) throw "\nInvlaid Input(s)\n";
	}catch(const char *s)
	{
		puts(s);
		return;
	}

	double here=1;
	double max=0;	
	int i;

	for(i=0;i<n;i++)
	{
		here=(here*a[i]>here?here*a[i]:here);
		max=(here>max?here:max);
	}
	printf("%f\n",max);
}

It is an O(n) algorithm, essentially a simple modification of Kadane's algorithm for maximum sub-array sum.

This question doesn't sound right. Were you asked the contiguous subarray?

If the question is what's asked here then,

0. Initialize index_z = 0, index_p = N
1. Sort the array.
2. Set the index of first zero (index_z) and the first positive number (index_p)
3. If index_z is nonzero,
3.a if index_z = 0, then PN = 1
3.b. else if the index_z is odd, then calculate the product PN = [0, index_z).
Note that, index starts from zero, so odd index means even number of elements, and vice versa.
3.c. else (if index_z is even) calculate product PN = (0, index_z), i.e., both index 0 and index_z are exclusive.
4. Calculate the product PP = (index_p, n)
5. Return (PP * PN)

There is one edge case where all the numbers can be zero, so initialize index_p to N initially before step 2.