Microsoft Interview Question






Comment hidden because of low score. Click to expand.
2
of 2 vote

Let's assume that array doesn't contain 0. Then we scan each element keeping following:
- total product of all elements
- index of first negative element and product of all elements before it (including itself)
- index of last negative element and product of all elements after it (including ifself)
In the end of cycle if total product is positive - print it
If negative than max product is either comes from begin of array till last negative element or from first negative element to end of array
In case array contains 0-s, we can just keep track of max sum comparing results obtained from subarrays divided by 0s.
Code below works for errays without, but can be easily modified for 0.

int A[] = { 4, -5, -3, 6, 2, -1, 3, 8 };

int multBeforeNeg = 1;
int multAfterNeg = 1;
int mult = 1;
int firstNegInd = -1;
int lastNegInd = -1;

for(int i=0;i<sizeof(A)/sizeof(int); ++i)
{
	mult *= A[i];

	if (A[i] < 0)
	{
		if (firstNegInd == -1) 
		{ 
			multBeforeNeg = mult; 
			firstNegInd = i; 
		}
		lastNegInd = i;
		multAfterNeg = 1;
	}

	if (firstNegInd != -1)
		multAfterNeg *= A[i];
}

if (mult>0)
	std::cout<<0<<"-"<<sizeof(A)/sizeof(int)-1<<":"<<mult;
else
	if (abs(multBeforeNeg)>abs(multAfterNeg))
		std::cout<<0<<"-"<<lastNegInd-1<<":"<<mult/multAfterNeg;
	else
		std::cout<<firstNegInd+1<<"-"<<sizeof(A)/sizeof(int)-1<<":"<<mult/multBeforeNeg;

- Zerg July 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cool! It seems most elegant and efficient solution.

- anon July 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, best solution.

- Anonymous July 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice.

- Anonymous August 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

ideone.com/m5fPS

#include <stdio.h>
#include <string.h>

const int MaxSize = 1000;
int data[MaxSize + 1];

int getMax(int a, int b){return a > b ? a : b;}
int getMin(int a, int b){return a < b ? a : b;}

int GetMaxPro(int *data, int n)
{
    int max = 1;
    int min = 1;
    int ret = 0;
    for(int i = 0; i < n; i ++)
    {
        if(data[i] > 0)
        {
            max = max * data[i];
            min = getMin(min * data[i], 1);
        }
        else if(data[i] == 0)
        {
            max = 1;
            min = 1;
        }
        else /* data[i] < 0 */
        { 
            max = getMax(min * data[i], 1);
            min = getMin(min * data[i], data[i]);
        }
        ret = getMax(ret, max);
    }
    return ret;
}
   
int main()
{
    int n;
    while(scanf("%d", &n) == 1)
    {
        for(int i = 0; i < n; i++)
        { 
            scanf("%d", &data[i]);
        }
        int ret = GetMaxPro(data, n);
        printf("ret = %d\n", ret);
    }
    return 0;
}

- wangxuyang September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey85087" class="run-this">int getMaxProductSubArray(int *arr, int nLength)
{
if (NULL == arr)
return -1;

int maxPre = arr[0], preAll = arr[0],maxSum = arr[0];
for (int i = 1;i < nLength;i++)
{
preAll = max(preAll*arr[i],arr[i]);
maxSum = max(maxPre,preAll);
maxPre = maxSum;
}
return maxSum;
}

</pre><pre title="CodeMonkey85087" input="yes">
</pre>

- Anonymous July 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, you can't just reuse the algorithm for sums.

- Anonymous July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I do not understand the question actually...
What does contigous elements here mean... does the product of subsequence to be found should be the product of elements which are in increasing order. or if the subsequence is not in increasing order, and the product of that subsequence is maximum, Then also we can output that subsequence.. Please clear my thoughts.. :)

- Anonymous July 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hey , it just asks u to return maximum product of continuous numbers in the array of whole numbers given.

{0,-1,-2,0,-4,-5,0,6,-1} ans=20 :)

- ktr July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

take 2 int32 arrays left[n], right[n] n=sizeof given array
left[0]=right[n-1]=1
now populate them as follows
for(int i=1;i<n;++i) left[i]=a[i-1]==0?1:a[i-1]*left[i-1];
for(int i=n-2;i>-1;--i) right[i]=a[i+1]==0?1:a[i+1]*right[i+1];

now for each element a[i] i=0 to n
result =result=max(result,left[i],right[i],a[i]*left[i]*right[i], left[i]*a[i],right[i]*a[i])

result would be our answer. but if all numbers are <1 then we find max in them and return it.

I guess this is O(n). suggest me if im wrong :)

- ktr July 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you take up an example.. that would be better i guess.. You simply coded, without explaining in words how are you trying to solve the problem??

- Anonymous July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Lets say we are given a list of nos. as follows::-
-2,1,-3,4,-4,2,1,-5,4,-1
1. In a first single pass we check the no. of negative integers or existence of 0. O(n)
Lets consider for this case, 0 does not exist. As 0 case can be handled with same idea.
If no 0 and even no. of -ve integers then Yippee!! The max product is the product of whole array. O(n).
2. If there are odd no. of -ve nos. then we select one with the smallest -ve no. and recurse on the left and right hand side of that -ve index to find the maximum product.

Same case can be done to handle if there are 0's in the array.

- Anonymous July 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Before posting soln, think twice, thrice and post.

- Sriram July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done in O(n) time and O(1) space.

1. Keep on multiplying the numbers till the next num is 0 or array end, keep track of the negative number whose absolute value is minimum.
2. Product obtained in step 1 is either -ve or +ve, if +ve then update the max product otherwise take left and right product from the number which was stored in step 1 and update the max product.
Please correct me if I am wrong. Below is the code

#include <stdio.h>
typedef struct
{
	int value;
	int index;
	int product;
}pivoteNode_t;
#define ABS(a) (((a)>0)?(a):(0-(a)))
void findMaxProduct (int* pArray, int size)
{
	pivoteNode_t pivoteNode={(1<<30),0,0};
	int product=1, maxProduct=0, rightProduct=0,leftProduct=0,i=0;
	while(i<size)
	{
		while((i<size)&&(pArray[i] != 0))
		{
			product=product*pArray[i];
			if((pArray[i]<0)&&(ABS(pArray[i]) < ABS(pivoteNode.value)))
			{
				pivoteNode.index=i;
				pivoteNode.product=product/pArray[i];
				pivoteNode.value=pArray[i];
			}
			i++;
		}
		if(product>0)
		{
			if(maxProduct<product)
			{
				maxProduct=product;
			}
		}
		else
		{
			leftProduct = pivoteNode.product*pivoteNode.value;
			rightProduct = product/pivoteNode.product;
			if(leftProduct>rightProduct)
			{
				if(maxProduct<leftProduct)
				{
					maxProduct=leftProduct;
				}					
			}
			else
			{
				if(maxProduct<rightProduct)
				{
					maxProduct=rightProduct;
				}						
			}
		}
		product=1;
		i++;
	}
	printf("Max Product: %d\n", maxProduct);
}
int main()
{
	int a[]={-2,1,-4,9,0,2,1,-5,4,-1,2,9,-3};
	findMaxProduct(a,sizeof(a)/sizeof(int));
	return 0;
}

- Anonymous July 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

One correction in the code at the end of while loop

product=1;
                pivoteNode.value=(1<<30);
		i++;

- Anonymous July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Elegant solution :)

- HiFi July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose, I have an array of whole numbers:
[-50,1,-3,-1,2,1,-2,-4]

From step 1, negative number = -1
From step 2, left product is 150 and right product is 16.
But, answer is 600 (discard -4 , multiply remaining elements)

- MP July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@MP:
Thanks for pointing out the mistake.
The algorithm can be corrected by one modification, instead of keeping track of only one -ve number I think if I'll keep track of all those product and the number where product is going to be -ve then it'll work and this can be done by the use of stack (or queue, or array).
Also since each product and element will be pushed and poped only once therefore the time complexity will still remain same but space complexity will be increased to O(n/2).
Let me know if there is still any flaw.

- Anonymous July 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have corrected the code after removing the bug in my logic as pointed by MP above. Please let me know if there is still some mistake.

#include <iostream>
#include <stack>
using namespace std;
typedef struct
{
	int value;
	int index;
	int product;
}pivoteNode_t;
void findMaxProduct (int* pArray, int size)
{
	int product=1, maxProduct=0, rightProduct=0,leftProduct=0,i=0;
	stack<pivoteNode_t*> pivoteStack;
	pivoteNode_t* pivoteNode;
	while(i<size)
	{
		while((i<size)&&(pArray[i] != 0))
		{
			product=product*pArray[i];
			if(product<0)
			{
				pivoteNode = new pivoteNode_t;
				pivoteNode->index=i;
				pivoteNode->product=product/pArray[i];
				pivoteNode->value=pArray[i];
				pivoteStack.push(pivoteNode);
			}
			i++;
		}
		if(product>0)
		{
			if(maxProduct<product)
			{
				maxProduct=product;
			}
			while(pivoteStack.empty()==false)
			{
				pivoteNode_t* ppivoteNode = pivoteStack.top();
				pivoteStack.pop();
				delete ppivoteNode;
			}
		}
		else
		{
			while(pivoteStack.empty()==false)
			{
				pivoteNode_t* ppivoteNode = pivoteStack.top();
				pivoteStack.pop();
				leftProduct = ppivoteNode->product;
				if(leftProduct < 0)
				{
					leftProduct = ppivoteNode->product*ppivoteNode->value;
				}
				rightProduct = product/ppivoteNode->product;
				if(leftProduct>rightProduct)
				{
					if(maxProduct<leftProduct)
					{
						maxProduct=leftProduct;
					}					
				}
				else
				{
					if(maxProduct<rightProduct)
					{
						maxProduct=rightProduct;
					}						
				}
				delete ppivoteNode;
			}
		}
		product=1;
		i++;
	}
	cout<<"Max Product:"<< maxProduct<<endl;
}
int main()
{
	int a[]={-50,1,-3,-1,2,1,-2,-4};
	findMaxProduct(a,sizeof(a)/sizeof(int));
	return 0;
}

- Anonymous July 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks right! But, can you tell why your time complexity is only O(n)? You loop through the same numbers in the inner and outer loops.

- R July 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

index i is increasing.
suppose when i=some value k then we come out from inner while loop.
At this point stack contains atmost k/2 items and we examined each item.
So when i=k we did 3k/2 operations.
similarly we did 3(n-k)/2 operations for remaning elements.
therefore we did total 3n/2 operations. therefore time complexity is O(n).

- Anonymous July 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I could think of this. Let me know if this is correct.

#include "stdafx.h"
#include <iostream>

int _tmain(int argc, _TCHAR* argv[])
{
int nums[] = {0,-1,-2,0,-4,-5,0,6,-1};
int nsize = sizeof(nums)/sizeof(int);
int prev = 1;
int maxPrev = nums[0] == 0 ? 1 : nums[0];
int maxProd = nums[0];
for (int i = 1; i< nsize; i++)
{
if(nums[i] == 0)
{
maxPrev = 1;
}
else
{
prev = nums[i] * maxPrev;
maxProd = maxProd > prev ? maxProd : prev;
maxPrev = prev;
}
}

std::cout << maxProd <<std::endl;
return 0;
}

- uk July 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain the solution in words rather than writing code...??

- MP July 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Incorrect.

- Anonymous July 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this:
1. Find all the 0s in the array, and chunk the array into subarrays, separated by 0. In the next step, we will find the biggest product from all the subarrays, unless all the subarrays are single negative numbers.
2. Same as the other solutions, we count the number of negative numbers in a subarray. If it is even, we are good, the whole subarray can be multiplied together. Otherwise we use the following algorithm.
3. In the "otherwise" case of 2, suppose the subarray is array[m..n]. We calculate the products left[n] and right[n]. left[i] is the product of array[m..i], and right[i] is the product of array[n-i..n-1]. For every other negative number, we compare the products of its left and right sub-subarrays. By doing this, we can find the sub-subarray with largest product.

I didn't put it in a well-organized way, just some hints. I think the time complexity is O(n), and space is also O(n).

Correct me if there are mistakes.

- Anonymous July 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It might be in right direction, only with some caveat.How would you deal with this input :

-9, -8, -2, 5, 6, -3, -5, -4

The largest product includes all elements, but I doubt your approach can handle this. Also how do you handle if input is like :

-9, -3, -2, 6, -7, -5, 1

we should take (-9) * (-3) * (-2) * 6 * (-7)

not, (-3) * (-2) * 6 * (-7)* (-5) * 1

It'd be better if you could code it, and post the link to verify.

- anon July 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In mathematics, natural numbers are the ordinary counting numbers 1, 2, 3, .. The question is incorrect. Natural numbers can't be negative.

- m@}{ July 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

man!! u have solved the question.

- Anonymous July 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lolzzzzz

- xyz July 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findMaxProd(int[] arr){

int prodmaxsofar = 1;
int prodmax = 1;
boolean sign = false;

for(int i = 0; i<arr.length;i++){
prodmaxsofar = prodmaxsofar * arr[i];
if(prodmaxsofar > prodmax){
prodmax = prodmaxsofar;
}else if(prodmaxsofar < 0){
if(i!=arr.length-1){
if(arr[i+1] < 0){
continue;
}else{
prodmaxsofar = 1;
}
}
}
}
System.out.println(prodmax);
}

- abc July 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hey smartAss, why don't u test ur code with atleast 10 random inputs. Learn yourself first, then share your solution with others!

- anon July 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looks like the solution I thought of was given earlier, in code. Here it is in writing:

Let A be an array of n elements, and suppose A[i_j] = 0 for j = 1, ..., r (there are r zeros in A), i_0 = 0 (A is zero-indexed).

Let maxProduct represent the greatest contiguous product found so far; maxProduct = 0 initially. Repeat the following steps for j running over 1 <= j <= r:

1. Let 1 <= j <=r and neg_num_j be the number of negative integers in the subarray A[i_{j-1}... i_{j}].
1.1 If neg_num_j is even, compare the product of all elements in the subarray to maxProduct (it will be non-negative) and replace maxProduct if we have found something greater.
1.2 If neg_num_j is odd, compare the product of all elements in A[i_{j-1}+1... i_{j}-2] to the product of all elements in A[i{j-1}+2...i_{j}-1], and take the max. Compare this max to maxProduct and take the greater of the two.

Of course, if 0 comes up repeatedly we just keep iterating until we hit a non-zero element. As has been said, this algorithm is O(n) time complexity, O(1) space.

- magritte128 July 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I made a mistake. Corrected version:

Let A be an array of n elements, and suppose A[i_j] = 0 for j = 1, ..., r (there are r zeros in A), i_0 = 0 (A is zero-indexed).

Let maxProduct represent the greatest contiguous product found so far; maxProduct = 0 initially. Repeat the following steps for j running over 1 <= j <= r:

1. Let 1 <= j <=r and neg_num_j be the number of negative integers in the subarray A[i_{j-1}... i_{j}].
1.1 If neg_num_j is even, compare the product of all elements in the subarray to maxProduct (it will be non-negative) and replace maxProduct if we have found something greater.
1.2 If neg_num_j is odd, let n_1 denote the index of the first negative number occurring in A[i_{j-1}... i_{j}] and n_2 the index of the last negative number occurring in A[i_{j-1}... i_{j}]. Compare the product of all elements in A[i_{j-1}+1... i_{n_2}-1] to the product of all elements in A[i_{n_1}+1...i_{j}-1], and take the max. Compare this max to maxProduct and reassign maxProduct to the greater of the two.

If 0 comes up repeatedly we just keep iterating until we hit a non-zero element. This algorithm is O(n) time complexity, O(1) space.

- magritte128 July 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ugh.. in 1.2, it should be A[i_{j-1}+1... n_2-1] compared to A[n_1+1, i_{j}-1]..

- magritte128 July 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In 1.1, I mean the product of all elements in A[i_{j-1}+1... i_{j}-1]. Obviously we don't want to include a 0.

- magritte128 July 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void maxProductSubArray(int *arr, int len, int *start, int *end, int *maxSum );

int main()
{
//maxProductSubArray
int arr[] = {0, -1, -2, 0, -4, -5, 0, 6, -1 };
int size = sizeof(arr)/sizeof(int);
int startIndex = 0, endIndex = 0, maxProd = 0;
maxProductSubArray(arr, size, &startIndex, &endIndex, &maxProd);
for(int i=startIndex; i<= endIndex ; i++)
printf("%d\t",arr[i]);
return 0;
}

/* Calling this method to find out subarray with max product
method will retrun integer array with start index and end index of max prod */
void maxProductSubArray(int *arr, int len, int *start, int *end, int *maxProd )
{
int maxProdSoFar = 0;
int curProd = 1;
int a = 0, b = 0, s = 0, i = 0;
for( i = 0; i < len; i++ )
{
curProd *= arr[i];
if ( curProd > maxProdSoFar )
{
maxProdSoFar = curProd;
a = s;
b = i;
}
if( curProd <= 0 )
{
if(curProd == 0)
{
curProd = 1;
s = i + 1;
}

}
}
*start = a;
*end = b;
*maxProd = maxProdSoFar;
}

Please correct me if any thing wrong in this above solution. Its O(n) solution.

- Shiva July 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Think can be solved using DP. Here is some direction.
At every location i we can get maximum product in two ways:-
1) if A[i] is positive then (maximum possible product at A[i-1])*A[i]
2) if A[i] is negetive then (minimum possible product at A[i-1])*A[i]

Therefore, for every location i we maintain maximum possible product array MA and minimum possible product array MI.
The maximum product can then be found by finding maximum value in MA

Time complexity : O(n)
Sapce complexity : O(n)

- Anonymous July 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

work first on paper rather posting crappy solution here!

- hmm July 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please comment on the mistake in the solution than posting a crappy comment...
I think it works...

- Anonymous August 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<malloc.h>
int maxprod(int a[],int n){
int max=a[0]*a[1];
int max1;
for(int i=1;i<n;i++){
max1=a[i]*a[i+1];
if(max1>max)
max=max1;
}
return max;
}

void main(){
int a[]={2,3,0,3,5,-4,-3,-6,-5,22,4,3,9,-7,-4,-6,0,0,9,45};
int h;
h=maxprod(a,sizeof(a)/sizeof(int));
printf("%d",h);
}

- anonymous123 July 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nothing but stupid asshole!

- hmm July 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution:
Keep three variables: maxProdEndingHere minProdEndingHere and maxProdSoFar

maxProdEndingHere = minProdEndingHere = maxProdSoFar = Arr[0]

for(i=1; i<n; i++)
{
....if(A[i] > 0)
....{    maxProdEndingHere = maxProdEndingHere * A[i];
.........minProdEndingHere = MAX( minProdEndingHere * A[i], minProdEndingHere);
.........maxProdSoFar =      MAX(maxProdEndingHere, maxProdSoFar);
....}
....else if(A[i] < 0)
....{    maxProdEndingHere = MAX( minProdEndingHere * A[i], 1);
.........minProdEndingHere = MAX( maxProdEndingHere * A[i], minProdEndingHere);
.........maxProdSoFar =      MAX(maxProdEndingHere, maxProdSoFar);
....}
....else //When A[i] == 0
....{
........maxProdEndingHere = 1;
........minProdEndingHere = 1;
........maxProdSoFar =      MAX(maxProdEndingHere, maxProdSoFar);
....}
}

Example:
Arr:              5 10  -6    -8    -1     3       4       -2     0     20     10
maxProdEndingHere 5 50   1   2400    8     24      96     57600   1     20     200
minProdEndingHere 5 5  -300   -8   -2400  -7200  -28800    -198   1     20     20    
maxProdSoFar      5 50  50   2400  2400    2400    2400   57600  57600 57600  57600

- Dee July 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A little modification
minProdEndingHere may not actually be lowest minimum, it's just a temporary used to construct maxEndingHere.


Correct Solution:

O(n) solution:
Keep three variables: maxProdEndingHere minProdEndingHere and maxProdSoFar


maxProdEndingHere = minProdEndingHere = maxProdSoFar = Arr[0]



for(i=1; i<n; i++)
{
    if(A[i] > 0)
    {    maxProdEndingHere = maxProdEndingHere * A[i];
         minProdEndingHere = MAX( minProdEndingHere * A[i], minProdEndingHere);
         maxProdSoFar =      MAX(maxProdEndingHere, maxProdSoFar);
    }
    else if(A[i] < 0)
    {    maxProdEndingHere = MAX( minProdEndingHere * A[i], 1);
         minProdEndingHere = maxProdEndingHere * A[i];
         maxProdSoFar =      MAX(maxProdEndingHere, maxProdSoFar);
    }
    else //When A[i] == 0
    {
        maxProdEndingHere = 1;
        minProdEndingHere = 1;
        maxProdSoFar =      MAX(maxProdEndingHere, maxProdSoFar);
    }
}



Example:
Arr:              5 10  -6    -8    -1     3       4       -2     0     20     10
maxProdEndingHere 5 50   1   2400    8     24      96     57600   1     20     200
minProdEndingHere 5 50 -300   -8   -2400  -7200  -28800    -198   1     20     200    
maxProdSoFar      5 50  50   2400  2400    2400    2400   57600  57600 57600  57600

- Dee July 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

soln looks nice. can you please put bit comments and the logic of ur code.

- neo August 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is correct code, but needs to explain some maths here.
btw: it needs to input the value of the 3 variables for the first 2 elements. That means, it is tricky to decide the values for the first 2 elements, not the first one element. After that, everything is easy.

- returning September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int product ( int a[] , int n )
{
int max_prdct =0 , prdct = 0;
int i ;
for( i=0 ; i< n ; i++ )
{
if( a[i]==0 )
if(max_prdct < prdct )
max_prdct = prdct ;
if( prdct == 0 )
prdct = a[i] ;
else
prdct *= a[i] ;
if( prdct > max_prdct )
max_prdct = prdct ;
}

if( prdct > max_prdct )
return prdct ;
return max_prdct ;
}

main ()
{
int num[11] ;
int i ;
for (i=0 ; i< 11; i++ )
{
printf("enter the number \n");
scanf ("%d" , &num[i] );
}
printf("%d" , product (num , 11 ) ) ;

}

- anonymous August 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int product ( int a[] , int n )
{
int max_prdct =0 , prdct = 0;
int i ;
for( i=0 ; i< n ; i++ )
{
if( a[i]==0 )
if(max_prdct < prdct )
max_prdct = prdct ;
if( prdct == 0 )
prdct = a[i] ;
else
prdct *= a[i] ;
if( prdct > max_prdct )
max_prdct = prdct ;
}

if( prdct > max_prdct )
return prdct ;
return max_prdct ;
}

main ()
{
int num[11] ;
int i ;
for (i=0 ; i< 11; i++ )
{
printf("enter the number \n");
scanf ("%d" , &num[i] );
}
printf("%d" , product (num , 11 ) ) ;

}

- anonymous August 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

P(i)
	if(i == 0)
		p = a[i]
		return a[i]
	else
		p= p*a[i]
		r = max(P(i-1)*i, p*i, i)
		if(r> um)
			um = r
		return r

Answer: um

- Prateek Caire September 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

similar to kadane's algo for sum

int currProduct = a[0];
int maxProduct = currProduct;
for (int i = 1; i < a.length; i++) {
       currProduct = currProduct * a[i];
       maxProduct = Math.max(currProduct, maxProduct);
       if ( currProduct == 0) {
            currProduct = 1;
       }
}

- anonymous July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I suspect the difference between this problem and the summation one is more than that. Consider {-1 2 3}. The output should be 6.

In the summation one, you can reset the current sum to 0 whenever it's negative. This problem seems harder because you can't do the same here due to input like {-2 -2}

- Sunny December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

0's can be handled by finding max product for subarrays split using 0 as delimiter. If the maximum product for each such subarray is negative then return 0. If not return the maximum product of the subarray

How to find maximum product of each subarray:
- For each index i, store a value which is the product of numbers till i (including i)
- Keep track of the following 
          - maximum product (positive) seen so far, say X
          - maximum negative product seen so far, say Y
          - least negative product seen so far, say Z
- Now if the final product (at last index) is positive return it
- If not return (X>(Z/Y)?X:(Z/Y))

- IntwPrep.MS December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think it should be "find the maximum SUM".

- AL July 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

SUM problem is known question everyone. This MULTIPLICATION is another form of the question.

- Anonymous July 07, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More