Author |
Topic: Largest product subarray (Read 3012 times) |
|
bazinga
Junior Member
Gender: 
Posts: 53
|
 |
Largest product subarray
« on: Apr 25th, 2011, 1:13am » |
 Quote  Modify
|
Given an array containing both +ve and -ve integer elements find the largest product of elements in a contiguous
subarray A[i .. j] .
| hidden: |
Is this correct.
Maintain two products +veP=0,-veP=0.
for each element in the array
{ if a[i] is -ve
{
+veP = -veP*a[i]
-veP = +veP(old one)*a[i]
if -veP becomes zero
-veP = a[i]
}
else
{
+veP = +veP*a[i]
-veP = -veP*a[i]
if +veP becomes zero
+veP =a[i]
}
if +veP> maxProduct
maxProduct = +veP
}//for loop
|
|
|
 IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Largest product subarray
« Reply #1 on: Apr 25th, 2011, 10:13pm » |
Quote Modify
|
How about something like this :
1) Group all continous +ve numbers as single +ve no. excluding zeroes.
2) Find pairs of continous -ve numbers. If no. of -ve nos. are odd, leave the one in the corner having lesser abs. value and multiply rest of them, and club the product with left +ve number.
3) Continue 1) and 2) steps till series look like ...
+ve -ve Zero +ve -ve Zero... Zero +ve
4) Zero has partitioned problem into subproblems
5) In each subproblem, number of -ve numbers are checked, and if odd last -ve number is excluded, and the product is taken.
6)Compare product for each subproblem and return the maximum.
|
| « Last Edit: Apr 26th, 2011, 3:09am by blackJack » |
IP Logged |
|
|
|
bazinga
Junior Member
Gender:
Posts: 53
|
|
Re: Largest product subarray
« Reply #2 on: Apr 26th, 2011, 12:50am » |
Quote Modify
|
Blackjack, would you mind giving a sample run of the algorithm with this array:
{ 9, -5, -6, -34, 45, 23, -5, -34, 12, 67 }
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Largest product subarray
« Reply #3 on: Apr 26th, 2011, 3:05am » |
Quote Modify
|
Quote:Blackjack, would you mind giving a sample run of the algorithm with this array:
{ 9, -5, -6, -34, 45, 23, -5, -34, 12, 67 } |
|
Step 1)
{ 9, -5, -6, -34, 45* 23, -5, -34, 12 * 67 }
= { 9, -5, -6, -34, 1035, -5, -34, 804 }
Step 2)
[if -ve nos. are odd, choose among the corner numbers and leave the one, having lesser abs. value, in this case, -5 will be left, -6 & -34 is paired]
{ 9, -5, -6* -34, 1035, -5*-34, 804 }
= { 9, -5, 204, 1035, 170, 804 }
= { 9, -5, 204, 1035* 170* 804}
= { 9, -5, 204* 1035* 170* 804}
Step 4) +ve -ve +ve
Step 5)
As only single -ve element is left,
return 204* 1035* 170* 804
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Largest product subarray
« Reply #4 on: Apr 26th, 2011, 3:52am » |
Quote Modify
|
Well, if we are dealing with integers, the more you multiply the larger the product. The only problem is with 0's and negative products.
So you need to examine separately every sequence of consecutive non-zero numbers. If the number of negatives is odd, you need to remove one. Try removing the leftmost -ve and then try the rightmost -ve.
You should stumble uppon tha largest number.
Now, if numbers are real numbers it is more difficult.
Again, consider every largest sequence of non-zero values. Compute the running product of all values from left to right. Keep the smallest positive and negative running product so far (smallest in absolute terms, i.e. closest to zero). These start at +1 and n/a.
At every step, compute (current product)/(smallest positive) if the product is >0 or (current product)/(smallest negative) if <0. The answer is the largest of these.
|
|
IP Logged |
|
|
|
bazinga
Junior Member
Gender:
Posts: 53
|
|
Re: Largest product subarray
« Reply #5 on: Apr 28th, 2011, 2:19am » |
Quote Modify
|
Thanks Blackjack. Thanks a lot Grimbal for explaining in detail.
Also I was wondering whether the following approach would work(how to prove that it is correct). We initialize two variables currentNegativeProduct and currentPositveProduct both to zero.
Now if we encounter a -ve number we set currentPositiveProduct to currentNegativePrdouct*currentElement and currentNegativeProduct to currentPositiveProduct*currentElement.If currentNegativeProduct becomes zero we set it to currentElement.And vice versa for a +ve element.
also if any time currentPositive product becomes less than 1 then we reset it to 0.
The maximum value achieved by currentPositiveProduct would be returned.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print