稻谷粒

用户名：uq_78133080422

访问量：3495

签　名：

等　　级
排　　名	2691
经　　验	2191
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

卢卡斯定理 & 快速幂算法 & 二项式定理解公式求值问题（Java代码）
浏览：2010

蓝桥杯2015年第六届真题-穿越雷区（简单的BFS）
浏览：379

你可能喜欢

蓝桥杯算法提高VIP-最大乘积-题解(Java代码)

　　作者: 稻谷粒　　　　发表时间：2021-03-18 23:16:17 浏览：254　|　评论：0　

原题链接：蓝桥杯算法提高VIP-最大乘积

f# [蓝桥杯] [算法提高VIP]最大乘积-题解(Java代码)

## 解题思路

- **1、读入n值时候，创建对应大小为n行2列的二维数组，每一行的第一个元素作为`符号位`：-1代表负数，0代表0，1代表正数，第二个元素存放键入的值的绝对值**
- 2、**利用选择排序按a[i] [1]降序排序**

- **3、使用贪心算法:每一次从剩余数字中选取绝对值最大的数字作为因数乘起来。每一次取值的时候记录取过的负数个数、绝对值最小负数下标、最小正数下标**

- 4、**分以下三种情况讨论：**
  - （1）取过的复数个数为偶数：此时上面的乘积结果即为最大值，直接return ；
  - （2）取过的复数个数为奇数且m<n：
    - a.取了奇数个负数，除以已取的最小负数，乘以剩下的最大正数 或者
    - b.除以已取的最小正数，乘以剩下的最大负数
     **取两种方案的最大值return**
  - （3）取过的复数个数为奇数且（m==n）:此时上面的乘积结果即为最大值的绝对值，直接return其相反数即可。

## 注意事项

**注意已经取过的最小整数为0时，那么就有m之后都为0，结果就是0**

## 代码实现

```java
import java.util.Scanner;
//最大乘积
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int group = scanner.nextInt();// 组数
		while (group > 0) {
			System.out.println(getMax(scanner));
			group--;
		}
		scanner.close();
	}
	public static int getMax(Scanner scanner) {
		int n = scanner.nextInt();// 该组总共的个数
		int m = scanner.nextInt();// 该组要取的个数
		int[][] arr = new int[n][2];// 符号位:数字 -1代表负数，0代表0，1代表正数

for (int i = 0; i < n; i++) {
			arr[i][1] = scanner.nextInt();
			if (arr[i][1] < 0) {
				arr[i][0] = -1;
				arr[i][1] *= -1;// 取正
			} else if (arr[i][1] > 0) {
				arr[i][0] = 1;
			}
		}
		// 按a[i][1]降序排序:选择排序
		for (int i = 0; i < n - 1; i++) {
			int maxIndex = i;// 记录最大下标
			for (int j = i + 1; j < n; j++) {
				if (arr[maxIndex][1] < arr[j][1]) {
					maxIndex = j;
				}
			}
			int[] temp = arr[maxIndex];
			arr[maxIndex] = arr[i];
			arr[i] = temp;
		}
		int count = 0;// 记录负数个数
		int max = 1;
		int minIndex = -1;// 记录选中的负数中绝对值最小的索引
		int minZIndex = -1;// 记录选中的正数中绝对值最小的索引(这里将0暂时归为正数)
		// 贪心算法:从剩余数字中选取绝对值最大的
		int k;
		for (k = 0; k < m; k++) {
			if (arr[k][0] < 0) {
				minIndex = k;
				count++;
			} else {
				minZIndex = k;
			}
			max *= arr[k][1];
		}
		if (count % 2 == 0) {// 取了偶数个负数，结果为正
			return max;
		} else if (count % 2 != 0 && m < n) {// 取了奇数个负数，除以已取的最小负数，乘以剩下的最大正数 或者
			// 除以已取的最小正数，乘以剩下的最大负数
			// 取两种方案的最大值
			if (minZIndex==-1||arr[minZIndex][1] == 0) {// 如果最后一个正数为0那么就有m之后都为0
				return 0;
			}
			int t1 = max / arr[minIndex][1];// 方案一
			int t2 = max / arr[minZIndex][1];// 方案二
			for (k = m; k < n; k++) {
				// 对方案一进行求最大值
				if (arr[k][0] > 0) {
					t1 = t1 * arr[k][1];
					break;
				} else if (arr[k][0] == 0) {
					t1 = t1 * arr[k][1];
					break;
				}
			}
			// 对方案二进行求最大值
			for (k = m; k < n; k++) {
				if (arr[k][0] < 0) {
					t2 = t2 * arr[k][1];
					break;
				}
				if (arr[k][0] == 0) {
					t2 = t2 * arr[k][1];
					break;
				}
			}
			return t1 > t2 ? t1 : t2;
		} else {// 取了奇数个负数，且m==n,结果为负
			return -max;
		}
	}
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

稻谷粒

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

蛇行矩阵（C语言代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

蓝桥杯算法提高VIP-最大乘积-题解(Java代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

【简单计算】（C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

1134题解(求分析)

幸运数（C++代码）

整数分类 oj上总是wrong answer

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

稻谷粒

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

蛇行矩阵 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

蓝桥杯算法提高VIP-最大乘积-题解(Java代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

【简单计算】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

1134题解(求分析)

幸运数 （C++代码）

整数分类 oj上总是wrong answer

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

蛇行矩阵（C语言代码）

C二级辅导-分段函数（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

【简单计算】（C语言代码）

幸运数（C++代码）