#include<stdio.h>
#include<conio.h>
int max_product(int a[], int len);
int main()
{
int a[]= {-10,4,-20,40,67,3};
int len = sizeof(a)/sizeof(int);
int mul = max_product(a,len);
printf("\n %d ",mul);
getch();
return 0;
}
int max_product(int a[],int len)
{
int i,j,k,min,temp;
int mul,mul1;
for(i=0;i<3;i++)
{
min = a[i];
for(j=i;j<len;j++)
{
if(a[j]<min)
{
min = a[j];
k=j;
}
}
a[k] = a[i];
a[i] = min;
}
for(i=0;i<len;i++)
printf("%d ",a[i]);
printf("\n");
for(i=0;i<3;i++)
{
for(j=3;j<len-i-1;j++)
{
if(a[j+1]<a[j])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for(i=0;i<len;i++)
printf("%d ",a[i]);
mul = a[len-1]*a[len-2]*a[len-3];
mul1= a[0]*a[1]*a[len-1];
if(mul<mul1)
return mul1;
else
return mul;
}
On Mon, Aug 8, 2011 at 5:10 PM, Prakash D <[email protected]> wrote:
> simple soln = max( product of lowest two negative numbers and highest
> positive number, product of highest three negative numbers, product of
> highest three positive numbers)
>
>
> On Mon, Aug 8, 2011 at 4:50 PM, Aditya Virmani
> <[email protected]>wrote:
>
>> what if we can maintain three arrays:
>> large_positives[3]: containing three largest positive numbers.,
>> large_negatives[2]: negative numbers with largest magnitude,
>> small_negatives[3]: negative numbers with least magnitudes.
>> Now thr may be following cases:
>> 1) No. of postive numbers >3 & no. of negative numbers>=2, thn max product
>> cud be, product of numbers in large_positives or product of largest positive
>> number with numbers in large_negatives.
>> 2) No. of positive numbers is 0(i.e all negatives), max product wud be
>> product of numbers in small_negatives.
>> 3)No. of positives is 1(though not required explicitly), product of
>> numbers in large_negatives with positive number.
>> 4) No. of positives is 2: max product wud be max of, product of two
>> positive numbers with small_negative or product of small_negatives.
>> Time complexity: O(n)
>> Space complexity: O(1)
>> I hope all the cases are covered, if not, please correct me
>>
>>
>> On Mon, Aug 8, 2011 at 4:40 PM, Aditya Virmani
>> <[email protected]>wrote:
>>
>>> what if the input is all negative?
>>>
>>> On Mon, Aug 8, 2011 at 12:57 PM, WgpShashank <[email protected]
>>> > wrote:
>>>
>>>> hey guys I think we can do it in O(N) Check out
>>>>
>>>> http://shashank7s.blogspot.com/2011/07/find-three-numbers-in-array-which-forms.html
>>>>
>>>> & let me know missed something ?
>>>>
>>>> Thanks
>>>> Shashank
>>>> CSE,BIT Mesra
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To view this discussion on the web visit
>>>> https://groups.google.com/d/msg/algogeeks/-/sC6zcqbh3ZUJ.
>>>>
>>>> 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?hl=en.
>>>>
>>>
>>>
>> --
>> 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?hl=en.
>>
>
> --
> 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?hl=en.
>
--
Regards
Aditya Pratap
--
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?hl=en.
