藍橋杯試題 算法提高 最大乘積 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;
	}
}