蓝桥杯-乘积最大
问题描述
给定N个整数A1, A2, … AN。请你从中选出K个数,使其乘积最大。请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以1000000009的余数。
代码片段
代码先放下面,明天再写写注释,太晚了23点17分 代码片
.
import java.util.Arrays;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main{
static long[][] dp;
static int text = 1000000009;
static int[] num;
static int N,K;
static long ans;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
N = scan.nextInt();
K = scan.nextInt();
num = new int[N+1];
dp = new long[N+1][2];
int[] tmp_num = new int[N];
for (int i = 0; i <N; i++) {
tmp_num[i] = scan.nextInt();
}
Arrays.sort(tmp_num);
//初始化dp数组
for (int i = 1; i <= N; i++) {
num[i] = tmp_num[i-1];
}
if (K==1){
System.out.println(num[N]);
return;
}
dp[1][0] = num[N]>=0?num[N]:-1;
dp[1][1] = num[1]<0?num[1]:1;
int index=2;
int l0=1,r0=N-1,l1=2,r1=N;
int[] tmp = new int[2];
while(index<=K){
tmp[0] = l0;
tmp[1] = r0;
if (dp[index-1][1]>0){
dp[index][0] = dp[index-1][1]*num[r1];
r0 = r1-1;
}else{
if (dp[index-1][1]*num[l1]>=dp[index-1][0]*num[r0]){
dp[index][0] = dp[index-1][1]*num[l1];
l0 = l1+1;
r0 = r1;
}else{
dp[index][0] = dp[index-1][0]*num[r0];
r0 = r0-1;
}
}
if (dp[index-1][1]*num[r1] < dp[index-1][0]*num[tmp[0]]){
dp[index][1] = dp[index-1][1]*num[r1];
r1=r1-1;
}else if(dp[index-1][0]*num[tmp[1]] < dp[index-1][0]*num[tmp[0]]){
dp[index][1] =dp[index-1][0]*num[tmp[1]];
l1 = tmp[0];
r1 = tmp[1]-1;
}else{
dp[index][1] =dp[index-1][0]*num[tmp[0]];
l1=tmp[0]+1;
r1=tmp[1];
}
if (dp[index][0]>text) dp[index][0] %=text;
if (dp[index][1]<-text) dp[index][1] = -((-dp[index][1])%text);
index++;
}
ans = dp[K][0]>0?dp[K][0]%text:-((-dp[K][0])%text);
System.out.println((int)ans);
scan.close();
}
}