Microsoft Interview Question
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;
}
<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>
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.. :)
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 :)
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.
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;
}
One correction in the code at the end of while loop
product=1;
pivoteNode.value=(1<<30);
i++;
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:
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.
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;
}
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.
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).
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;
}
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.
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.
In mathematics, natural numbers are the ordinary counting numbers 1, 2, 3, .. The question is incorrect. Natural numbers can't be negative.
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);
}
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.
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.
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.
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)
#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);
}
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
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
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 ) ) ;
}
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 ) ) ;
}
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;
}
}
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}
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))
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.
- Zerg July 09, 2011