题目描述
对于n个数,从中取出m个数,如何取使得这m个数的乘积最大呢?
输入
第一行一个数 代表数据组数
每组数据共两行
第一行两个正整数n、m, n,m<=20
第二行给出n个整数,其中每个数的绝对值小于4
输出
每组数据输出1行,为最大的乘积
样例输入
1
5 5
1 2 3 4 2
样例输出
48
参考代码
#include<stdio.h>
int main()
{
int i,t;
long long sum=1;
int a[66];
int x,y;
int n,m;
int h=0;
scanf("%d",&y);
while(y--)
{
sum=1;
h=0;
scanf("%d%d",&n,&m);
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]>0)
h++;
}
for (i=0;i<n;i++)
for (t=0;t<n-1;t++)
{
if(a[t]>a[t+1])
{
x=a[t];
a[t]=a[t+1];
a[t+1]=x;
}
}
if(m%2!=0)
{
if(a[n-1]<0)
for (i=n-m;i<n;i++)
sum=sum*a[i],m=0;
}
long long int b,c;
i=0;
t=n-1;
while(m)
{
b=a[i]*a[i+1];
c=a[t-1]*a[t];
if(b>=c&&m>=2)
sum=sum*b,i+=2,m-=2; else
sum=sum*a[t],t--,m--;
}
printf("%lldn",sum);
}
return 0;
}
解析
暂无