本文共 3017 字，大约阅读时间需要 10 分钟。

从n个数中取m个使得乘积最大？

问题描述

　　对于n个数，从中取出m个数，如何取使得这m个数的乘积最大呢？

输出格式

样例输出

算法设计

package com.bean.algorithmbasic;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.util.ArrayList;import java.util.Collections;import java.util.Scanner;public class LargestProduct {    /*     * 问题描述     * 对于n个数，从中取出m个数，如何取使得这m个数的乘积最大呢？     *      * 输入格式     *      * 第一行一个数表示数据组数     * 每组输入数据共2行：     * 第1行给出总共的数字的个数n和要取的数的个数m，1<=n<=m<=15，     * 第2行依次给出这n个数，其中每个数字的范围满足:a[i]的绝对值小于等于4。     *      * 输出格式     *      * 每组数据输出1行，为最大的乘积。     * */    public static long n, m, temp;    public static ArrayList
   
     list = new ArrayList
    
     ();// 存放输入的数    public static ArrayList
     
       result = new ArrayList
      
       ();    /*     * 注意题目只说了对于n个数，从中取出m个数，并没有说明这些数是正数、负数还是0.     * 分析：负数要想选择，必须两个两个的选择。     * 正数只需要一个一个选择就好~     * 所以把数组按照从小到大排序，这样负数就在最左边，正数就在最右边啦~     * 当还可以选择两个或者两个以上数字的时候~     * 比较两个左边的数字相乘会不会比右边的数字相乘的结果大~     * 如果大的话，那就选左边那两个负数~     * 如果只能选择一个数字了，或者左边两个数的乘积不比右边两个数的乘积大~     * 那么就选择最右边那个最大数字就好~     * 相乘得到结果~~     * */    public void computeLargestProduct() {        //对读取的列表中的元素进行排序        Collections.sort(list);        //        for (int i = 0, j = list.size() - 1; m > 0;) {            if (m >= 2) {                long a1 = list.get(i) * list.get(i + 1);                long a2 = list.get(j) * list.get(j - 1);                //                if (a2 > a1) {                    temp *= list.get(j);                    j--;                    m--;                } else {                    temp *= a1;                    i = i + 2;                    m = m - 2;                }            } else {                if (m == 1) {                    temp *= list.get(j);                    j--;                    m--;                }            }        }        result.add(temp);    }    public static void main(String[] args) throws FileNotFoundException {        //程序开始执行时间        long startTime=System.currentTimeMillis();        LargestProduct test = new LargestProduct();        System.setIn(new FileInputStream("G:\\LargestProduct.txt"));        Scanner sc = new Scanner(System.in);        int t = sc.nextInt();        while (t > 0) {            t--;            //读取N，代表一共有n个数            n = sc.nextLong();            //读取M，代表从n个数中取出m个数            m = sc.nextLong();            // 赋初值为1            temp = 1;            //清空list            list.clear();            //读取n个数，并且装入list中            for (int i = 0; i < n; i++) {                long a = sc.nextLong();                list.add(a);            }            //计算            test.computeLargestProduct();        }        for (int i = 0; i < result.size(); i++)            System.out.println(result.get(i));        //程序执行结束时间        long endTime=System.currentTimeMillis();        System.out.println("程序执行时间: "+(endTime-startTime)+" ms");    }}
      
     
    
   

（完）

转载地址：http://mgvdi.baihongyu.com/