蓝桥杯算法提高VIP-最大乘积(dfsn个选k个的模板题--直接记住模板)

参考代码:

import java.util.*;

public class Main {//组合型

static int n;

static int r;

static int[]arr=new int[1000];

static int[]p=new int[1000];

static int count;

static int max=-(int)1e9;

public static void main(String[]args) {

Scanner input=new Scanner(System.in);

int k=input.nextInt();

while(k>0) {

n=input.nextInt();

r=input.nextInt();

for(int i=1;i<=n;i++)p[i]=input.nextInt();

dfs(1,1);

System.out.println(max);

max=-(int)1e9;

k--;

}

}

public static void dfs(int x,int start) {

if((x-1)+(n-start+1)<r)return;/*剪枝 x-1表示当前位置以及放置的个数

                                 n-start+1表示剩下要排的个数 组合的剪纸                        */

if(x>r) {

int sum=1;

for(int i=1;i<=r;i++) {

sum*=arr[i];

}

max=Math.max(sum, max);

}

for(int i=start;i<=n;i++) {//start表示有多个分支

arr[x]=p[i];

dfs(x+1,i+1);//这里i+1保证前一个数一定大于后一个数比如123.

arr[x]=0;

}

}

}