首页 > 代码库 > C语言 · 最大乘积

C语言 · 最大乘积

  算法提高 最大乘积  
时间限制:1.0s   内存限制:512.0MB
    
问题描述
  对于n个数,从中取出m个数,如何取使得这m个数的乘积最大呢?
输入格式
  第一行一个数表示数据组数
  每组输入数据共2行:
  第1行给出总共的数字的个数n和要取的数的个数m,1<=n<=m<=15,
  第2行依次给出这n个数,其中每个数字的范围满足:a[i]的绝对值小于等于4。
输出格式
  每组数据输出1行,为最大的乘积。
样例输入
1
5 5
1 2 3 4 2
样例输出
48 

解题思路:输入数组,先排序,将处理后的数组的前m个数的积输出。
 1 #include<stdio.h>
 2 void MaoPao_Down(int a[], int n)
 3 {
 4     int i, j, temp;
 5     for (j = 0; j < n - 1; j++)
 6         for (i = 0; i < n - 1 - j; i++)
 7          if(a[i] < a[i + 1])
 8             {temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;}
 9 }
10 int main(){
11     int count;
12     int n,m;
13     
14     int a[20];
15     scanf("%d",&count);
16     while(count--){
17         scanf("%d%d",&n,&m);
18         for(int i=0;i<n;i++){
19             scanf("%d",&a[i]);
20         }
21         int JI=1,temp1,temp2;
22         MaoPao_Down(a,n);
23         for(int j=n-1,k=0;m>0;){
24             if(m>=2){
25                 temp1 = a[j]*a[j-1];
26                 temp2 = a[k]*a[k+1];
27                 if(temp1>=temp2){
28                     JI*=temp1;
29                     m-=2;
30                     j-=2;
31                 }else{
32                     JI*=a[k++];
33                     m--;
34                 }
35             }else {  
36                 JI*=a[k++];
37                 m--; 
38             } 
39         }
40         printf("%d",JI);
41         printf("\n");
42     }
43 }

 

 

C语言 · 最大乘积