Let X = {x1, x3, ..., xn} be a sequence of arbitrary real numbers. Give a linear time algorithm to find the subsequence of consecutive elements xi, xi+1 , ..., xj whose product is maximum over all consecutive subsequences. The product of the empty subsequence is defined as 1. Observe that X can contain reals less than 1, including negative
numbers.
maxProduct(a[]){
lef tP osP rod = 1 // product of the right positive segment
rightP osP rod = 1 //product of the left positive segment
lef tN egative = U N DEF IN ED //value of the left-most negative
rightN egative = U N DEF IN ED //value of the right-most negative
totalP rod = 1 //product of entire array
negCount = 0 //keeps track of the number of negatives encountered
for(i = 0; i < a.size; i + +;){
totalProd ∗ = a[i]
if(a[i] > 0 and lef tN egative = U N DEF IN ED)
leftPosProd ∗ = a[i]
else if(a[i] > 0 and rightN egative = U N DEF IN ED)
rightPosProd ∗ = a[i]
else if(a[i] < 0 and lef tN egative = U N DEF IN ED){
negCount + +
rightN egative = a[i]
rightP osP rod = 1
}
else //a[i] is the first negative encountered
negCount + +
lef tN egative = rightN egative = a[i]
}
}
if((negCount > 0 and a.size = 1) or negCount %2 = 0)
return totalP rod
else
return totalP rod/minimum(leftPosProd*leftNegative,rightPosProd*rightNegative)
maxProduct :: RealFrac a => [a] -> a
maxProduct = f 1 1 1
where
f maxp _ _ [] = maxp
f maxp mina a (x:xs) =
let a' = a * x
p = a' / mina
in f (max maxp p) (min mina a') a' xs
Anyway, what I was thinking of was that I have to split arrays to get rid of the 0s. And I will have a sub array. And this array can have either an even or odd number of negatives. If it is an even number of negatives, I just calculate the product. If there are an odd number of negatives I divide the product by the front until I hit the negative number, then I save that as temp1, I go back to the original product and divide by the last number working backwards until I hit the first negative number and save that as temp2, and then I can just return the max of temp1,temp2.
-Split array into sub-arrays between zeros. (O(n))
-Check how many negative numbers each sub-array has. (O(n))
-If even, then multiply out the whole sub-array. (O(n))
-If odd, then you would have two products: one using everything after the first negative number and one using everything before the last negative number. Take the larger of the two. (O(n))
-Find the largest value out of all the sub-arrays. (O(n))
Name:
Anonymous2010-08-29 10:26
>>17
there can be up to 10,000 elements in the array, so I should probably use bigInteger
>>18
-If odd, then you would have two products: one using everything after the first negative number and one using everything before the last negative number. Take the larger of the two. (O(n))
that makes more sense than doing all the calculations and then dividing out. But I would have to have a location of the last negative before I start doing the product?
Name:
Anonymous2010-08-29 10:38
so I can make a function
product(ar[],start,end)
findFirstNeg(ar[]){...}
findLastNeg(ar[]){...}
then
temp = product(ar,0,findLastNeg)
temp2 = product(ar,findFirstNeg,ar.length-1)
return(temp>temp2?temp1:temp2)
calculate product from initial condition until it hits a 0
if that product is positive, check if it is bigger than max, set it true
if negative
set total product to temp1 and temp2
divide temp1 by the start until it is positive
divide temp2 by the end backwards until it is positive
compare Max(temp1 ,temp2 ) to max, set if true
continue until end of loop
this runs in O(n^2) time from experimental data, though I thought it would have been O(n)
Name:
Anonymous2010-09-08 15:23
use jewlib
Name:
Anonymous2010-09-08 15:58
Jewish liberation ?
Name:
Anonymous2010-09-08 19:27
>>39
You might just be seeing the breakdown of your ``multiplication and division are O(1) time'' assumption. The divisions can be replaced by keeping both negative and positive running totals.
Name:
Anonymous2010-09-08 21:29
>>42
The divisions can be replaced by keeping both negative and positive running totals.