|
Given an array of natural numbers....
Microsoft Interview Questions and Answers
(Continued from previous question...)
69. Given an array of natural numbers....
Question:
Given an array of natural numbers (+ve, 0, -ve integers), find the maximum product of contiguous elements. Product value won't overflow 32 bits. Efficient solution ( O(nlogn) or better) is needed.
maybe an answer:
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<<"-"<
(Continued on next question...)
Other Interview Questions
| 