1239. 乘积最大 Java题解 （模拟，贪心，双指针）【第九届蓝桥杯省赛C++B组】

输入样例1：

5 3
-100000
-10000
2
100000
10000

输出样例1：

999100009

输入样例2：

5 3
-100000
-100000
-2
-100000
-100000

输出样例2：

-999999829

解题思路：

分类讨论：（假设数组已从小到大有序）

一.   k == n 时，最大值就是所有数的乘积。

二 . ① k < n 时，且k为偶数：

• a. 假设负数有偶数个，因为负负得正，所以最大值一定使整数，且最大值取决于序列中最左端的两个数与最右端的两个数乘积的最大值。
• b. 假设负数有奇数个，因为 k < n，所以去掉一个负数后，剩下的负数就是偶数个，同样负负得正，所以最大值也一定是正数。
• -- >  结论：k为偶数，最大值一定为正数。

② k < n，且k为奇数：

• a. 当序列中都是负数时，最大值一定时负数，所以取有序序列的最右端k个数，即为最大值。
• b. 当序列中至少存在一个非负数时，最大值中一定包括最右端这个非负数，此时再选k-1个数即可，且k-1为偶数，所以和情况①的a相同。最大值为正数。
• -- >结论：k为奇数时，只有序列中均为负数，最大值才会为负数。

求有序序列中k为偶数个的最大值：（双指针思想）

 序列最左端为l，序列最有端为r，因为负数乘以负数才会为正数，所以左端必须取连续的两个值，又因为取的k也是偶数，所以右端也取两个值。当左边两数乘积大于右边两数时，将左边两数累乘，并且左指针右移动两个单位，否则 右指针左移两个单位，直到k个数为止。

Java代码：

import java.io.*;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		final int N = 1000000009;
		int n = Integer.parseInt(split[0]);
		int k = Integer.parseInt(split[1]);
		int []arr = new int[n];
		
		for(int i = 0; i < n; i++) 
			arr[i] = Integer.parseInt(br.readLine());
		Arrays.sort(arr);
		
		long ans = 1;
		int sign = 1, l = 0, r = n - 1;  // sign用于标记正负数 l，r为左右指针
		if(k % 2 == 1) {  // 奇数时，最大的数必选，之后又和选偶数情况相同
			ans = arr[r--];
			k--;
			if(arr[n - 1] < 0) sign = -1;  // 最大值为负数，说明序列都是负数，而k又是奇数，要想使结果乘积最大，绝对值应最小
		}
		
		while(k > 0) {
			long x = arr[l]* arr[l + 1], y = arr[r] * arr[r - 1];  // x为左端点两个数，y为右端点两数，每次取一对
			if(x * sign > y * sign) { 
				ans = (x % N * ans) % N;
				l += 2;  //左指针右移
			}else {
				ans = (y % N * ans) % N;
				r -= 2;
			}
			k -= 2;
		}
		
		System.out.println(ans);
	}
}