每日一题之乘积最大

题目描述

给定 N 个整数 A1,A2,⋯AN。请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 109+9 的余数。

注意，如果 X<0，我们定义 X 除以 109+9 的余数是负(−X)除以 109+9的余数。

即：0−((0−x)%109+9)。

输入描述

输入格式：

第一行包含两个整数 N,K。

以下 N 行每行一个整数 Ai。

其中，1≤K≤N≤105，−105≤Ai≤105。

输出描述

输出一个整数，表示答案。

思路分析：

情况 1：`k == n`

如果 k == n，说明我们需要选择数组中所有的数。
此时，无论数组中的数是正数还是负数，最终的结果就是所有数的乘积。
不需要额外的选择策略。

情况 2：`k < n`

当 k < n 时，我们需要选择部分数。此时，我们需要根据 k 的奇偶性以及数组中负数的个数来决定选择策略。

子情况 1：`k` 是偶数

目标：选出的结果一定是非负数。
原因：
1. 如果负数的个数是偶数个，那么我们可以成对选择负数（负负得正），最终结果是非负数。
2. 如果负数的个数是奇数个，我们可以只选择偶数个绝对值最大的负数，剩下的选择正数，最终结果仍然是非负数。
策略：
- 使用双指针法，每次比较数组左端两个数的乘积和右端两个数的乘积，选择乘积较大的一对。
- 重复这个过程，直到选出 k 个数。

子情况 2：`k` 是奇数

目标：选出的结果可能是负数或非负数，取决于数组中的元素。
子情况分析：
1. 如果数组中所有数都是负数：
  - 选出的结果一定是负数。
  - 因为奇数个负数的乘积仍然是负数。
2. 如果数组中至少有一个非负数：
  - 我们可以先选择最大的一个数（一定是非负数），此时剩下的 k-1 个数是偶数个。
  - 问题转化为 k-1 是偶数的情况，按照偶数策略选择即可。
策略：
- 先选择数组中最大的一个数（如果存在非负数，则选择最大的非负数；否则选择最大的负数）。
- 然后对剩下的 k-1 个数，按照偶数策略选择。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 100010, M = 1000000009;  // 定义常量N和M，N为数组最大长度，M为模数
typedef long long ll;  // 定义long long类型为ll，方便使用ll a[N];  // 定义数组a，用于存储输入的整数
int n, k;  // n为数组长度，k为需要选择的元素个数
ll res = 1;  // 初始化结果为1，用于存储最终的乘积结果int main()
{cin >> n >> k;  // 输入数组长度n和需要选择的元素个数kfor(int i = 0; i < n; i++){cin >> a[i];  // 输入数组元素}sort(a, a + n);  // 对数组进行排序，方便后续处理int l = 0, r = n - 1;  // 定义双指针，l指向数组最左端，r指向数组最右端int sigh = 1;  // 符号标记，初始为1，表示结果为正数// 当k为奇数时，至少取一个最大的数while(k % 2){res = a[r];  // 取当前最大的数r--;  // 右指针左移k--;  // k减1，表示已经取了一个数if(res < 0) sigh = -1;  // 如果取的数为负数，则标记符号为-1}// 双指针法处理剩余的k个数while(k){ll x = a[l] * a[l + 1];  // 计算左端两个数的乘积ll y = a[r] * a[r - 1];  // 计算右端两个数的乘积// 根据符号标记和乘积大小决定取哪一对数if(x * sigh > y * sigh){res = x % M * res % M;  // 取左端的两个数，并更新结果l += 2;  // 左指针右移两位}else{res = y % M * res % M;  // 取右端的两个数，并更新结果r -= 2;  // 右指针左移两位}k -= 2;  // k减2，表示已经取了两个数}cout << res << endl;  // 输出最终结果return 0;  // 程序结束
}

代码实现思路

排序数组：
- 将数组排序，方便使用双指针法选择数。
处理 k 是奇数的情况：
- 先选择最大的一个数，并更新结果和符号标记。
- 将 k 减 1，转化为偶数情况。
处理 k 是偶数的情况：
- 使用双指针法，每次选择左端或右端乘积较大的一对数。
- 更新结果，直到选出 k 个数。
输出结果：
- 最终输出计算得到的乘积结果

总结：就是先判断k是奇数还是偶数，若是偶数，先取出最大的数，将k变为偶数。当k为偶数，我们只需要分别从左右两边去找最大的一对乘积，也就是看看到底是两个负数相乘的结果大还是两个正数相乘的结果大。

这道题的标签是动态规划，现在附上动态规划的代码，不过会超时。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int MOD = 1e9 + 9;  // 定义模数
const long long INF = 1e18;  // 定义无穷大int main() {int N, K;cin >> N >> K;vector<int> A(N);for (int i = 0; i < N; i++) {cin >> A[i];}// 初始化 DP 表vector<vector<long long>> dp(N + 1, vector<long long>(K + 1, -INF));dp[0][0] = 1;  // 从 0 个数中选出 0 个数，乘积为 1// 动态规划求解for (int i = 1; i <= N; i++) {for (int j = 0; j <= K; j++) {// 不选 A[i-1]dp[i][j] = dp[i - 1][j];// 选 A[i-1]if (j > 0 && dp[i - 1][j - 1] != -INF) {long long temp = dp[i - 1][j - 1] * A[i - 1];if (temp > dp[i][j]) {dp[i][j] = temp;}}}}// 输出结果long long result = dp[N][K];if (result < 0) {// 如果结果为负数，按照题目要求处理result = 0 - ((0 - result) % MOD);} else {result %= MOD;}cout << result << endl;return 0;
}

思路如下：

1. 定义状态

设 dp[i][j] 表示从前 i 个数中选出 j 个数，能够得到的最大乘积。
其中：
- i 表示当前考虑的前 i 个数。
- j 表示需要选出的数的个数。

2. 状态转移方程

对于每个数 A[i]，我们有两种选择：

不选 A[i]：
- 最大乘积仍然是 dp[i−1][j]。
选 A[i]：
- 最大乘积是 dp[i−1][j−1]×A[i]。

因此，状态转移方程为：

dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−1]×A[i])

3. 初始化

dp[0][0]=1：从 0 个数中选出 0 个数，乘积为 1。
dp[i][0]=1：从任意 i 个数中选出 0 个数，乘积为 1。
dp[0][j]=−∞（无效状态）：从 0 个数中选出 j个数是不可能的。

4. 最终结果

我们需要的结果是 dp[N][K]，即从前 N 个数中选出 K 个数的最大乘积。

代码解释

输入处理：
- 读取 N 和 K。
- 读取数组 A。
初始化 DP 表：
- dp[i][j] 表示从前 i 个数中选出 j 个数的最大乘积。
- 初始状态 dp[0][0]=1，其余状态初始化为负无穷（无效状态）。
状态转移：
- 对于每个数 A[i−1]，更新 DP 表。
- 如果不选 A[i−1]，则 dp[i][j]=dp[i−1][j]。
- 如果选 A[i−1]，则 dp[i][j]=dp[i−1][j−1]×A[i−1]。
结果处理：
- 如果结果为负数，按照题目要求处理。
- 如果结果为正数，直接取模。
输出结果：
- 输出最终的最大乘积。