蓝桥杯试题 算法提高 最大乘积 JAVA

试题 算法提高 最大乘积

资源限制

时间限制：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

思路：这道题用的递归来做的，一直在n个数中找m个相组合，然后找到最大的就行

代码如下：

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int z = sc.nextInt(), p = 0, ss = 0, sum = 1, c = -100 , c1=-100;
		int[] max = new int[z];
		while (z > 0) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			for(int i=0;i<=n-m;i++) {
				c = lc(a, i, n, ss, m, sum);
				if(c>c1) {
					c1=c;
				}
				ss=0;
			}
			max[p++] = c1;
			c1=0;c=0;
			z--;
		}
		sc.close();
		for (int i = 0; i < p; i++) {
			System.out.println(max[i]);
		}
	}

	public static int lc(int[] a, int i, int n, int ss, int m, int sum) {
		int temp=0,max=-10,max1 = -10;ss++;//这里max和max1要设置的小一点，否则会出现比零更小的结果
		for (int j = i; j < n; j++) {
			temp=sum;sum*=a[j];
			if(ss==m) {
				if(sum>max) {
					max=sum;
				}
			
			}else{
				max1=lc(a,j+1,n,ss,m,sum);
			}
			if(max1>max) {
				max=max1;
			}
			sum=temp;
		}
		return max;
	}
}