Assumption: Array has at least 3 numbers.
Solution:
Create two arrays of size 3. Lets say P[] & N[], where P[] going to hold the
top 3 +ve integers and N[] going to hold the top 3 -ve ( magnitude wise)
integers. [ i.e., P[0]<P[1]<P[2] .... N[0]<N[1]<N[2] ]
P.len & N.len has been maintained to get the current length of P[] & N[]
respectively. [ See the below algorithm to fill both the arrays
appropriately ] . Then, use the below logic to give the 3 numbers
a) If P.len ==0, obviously N.len = 3 ( coz of the
Assumption).............Return N[]
b) Else If P.len ==1, N.len >=2 ( coz of the Assumption ) ......
Return { P[2], N[1], N[2] }
c) Else if P.len ==2, N.len >=1 (coz of the Assumption); If
N.len == 1 Return { P[2], P[1], N[2] } else Return { P[2], N[1], N[2] }
d) Else (i.e., P.len == 3) , If (N.len == 0 OR N.len == 1 ) return
P[]
else
if ( N[2]*N[1] <
P[0]*P[1] )
return {
P[] }
else
return {
P[2]*N[1]*N[2] }
e) MASTER IF (use this condition before cond(a) ) if (P.len + N.len
< 3 ), return MaxPdt = 0. [ In the algo, 0 is not considered either as a
+ve int or -ve int. Condition (a) to (d) will hold if at all there exists 3
numbers other than X number of 0's in the array. If not, obviously result is
0 ] May be, we can return all the elements (i.e., 2 elements ) in P[] & N[]
and a 0 being the 3rd element.
Code snippet :
p.len = n.len = 0
for (i=0; i<N; i++)
{
if (S[i]>0)
{
if (p.len == 0 ) { P[2] = S[i]; p.len++; }
else if (p.len == 1 )
{
if (P[2] <= S[i]) { temp=P[2]; P[2]=S[i]; P[1]=temp; p.len++ }
else { P[1] = S[i]; p.len++ }
}
else if (p.len == 2 )
{
if (P[2] <= S[i]) { P[0]=P[1]; P[1]=P[2]; P[2]=S[i]; p.len++ }
else if (P[1] <= S[i]) { P[0]=P[1]; P[1]=S[i]; p.len++ }
else {P[0]=S[i]; p.len++
}
else
{
if (P[2] < = S[i]) { P[0]=P[1]; P[1]=P[2]; P[2]=S[i]; }
else if (P[1] <= S[i]) { P[0]=P[1]; P[1]=S[i]; }
else if (P[0] <= S[i]) { P[0]=S[i]}
}
}
if (S[i]<0)
{
S[i] = -S[i];
if (p.len == 0 ) { N[2] = S[i]; p.len++; }
else if (p.len == 1 )
{
if (N[2] <= S[i]) { temp=N[2]; N[2]=S[i]; N[1]=temp; p.len++ }
else { N[1] = S[i]; p.len++ }
}
else if (p.len == 2 )
{
if (N[2] <= S[i]) { N[0]=N[1]; N[1]=N[2]; N[2]=S[i]; p.len++ }
else if (N[1] <= S[i]) { N[0]=N[1]; N[1]=S[i]; p.len++ }
else {N[0]=S[i]; p.len++
}
else
{
if (N[2] < = S[i]) { N[0]=N[1]; N[1]=N[2]; N[2]=S[i]; }
else if (N[1] <= S[i]) { N[0]=N[1]; N[1]=S[i]; }
else if (N[0] <= S[i]) { N[0]=S[i]}
}
}
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
