A game company has designed an online lottery game, Bingo. In this game, N number cards are displayed. Each card has a value on it. The value can be negative or positive. The player must choose two cards. To win the game, the product of the values of the two cards must be the maximum value possible for any pair of cards in the display. The winning amount will be the sum of the two cards chosen by the player. Write an algorithm to find the winning amount as the sum of the values of the two cards whose product value is maximum.
Input
The first line of the input consists of an integer numCards, representing the number of cards (N). The second line consists of N space-separated integers – ….. , val1 , val2…., valN representing the values on the cards.
Output
Print an integer representing the sum of the values of the two cards whose product value is maximum.
Constraints
0<numCardss106
-106< vali<106
0< i <numCards
Example
Input:
7 9 -3 8 -6 -7 8 10
Output:
19
Explanation:
The maximum product of the values is 90, i.e. 9*10. So, the sum of the values of the selected cards is 19.
Solution: In C
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a[n],i,j,prod[n-1],t;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=0;i<n-1;i++)
{
prod[i]=a[i]*a[i+1];
}
int sum;
if(prod[0]>prod[n-2])
sum=a[0]+a[1];
else
sum=a[n-1]+a[n-2];
printf("%d",sum);
return 0;
}Also Checkout