Solution - 最大乘积

题目描述

给你 \(n\) 个整数 \(a_1、a_2、...、a_n\)，从中任意挑选出 \(n\) 个数字，使得乘积最大，输出乘积最大值。

输入格式

输入有多组测试数据。

第一行为整数 \(t\) ，表示测试数据组数。

每组测试数据第一行为整数 \(n\)，表示数字的数量。

每组测试数据第二行有 \(n\) 个整数 \(a_1、a_2、...、a_n\)。

输出格式

每组测试数据输出只有 \(1\) 个整数，表示挑选 \(5\) 出个数字的乘积最大值。

样例输入

4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1

样例输出

-120
12
0
945

数据范围与提示

\(1 ≤ t ≤ 100\)
\(5 ≤ n ≤ 10^5\)
\(-10^3 ≤ a_i ≤ 10^3\)

---

此题我来介绍一下 dp 做法。
首先看到数据范围我们就可以判断此题要用时间复杂度接近 \(\mathcal{O}(n)\) 的算法，所以我们联想的了线性 \(dp\)

所以我们定义
\(dp1_{i,j}\) 表示从前 \(i\) 个数选 \(j\) 个数字所得乘积的最大值。
\(dp2_{i,j}\) 表示从前 \(i\) 个数选 \(j\) 个数字所得乘积的最小值。
这里解释一下为什么要求最小值，如果当前遍历到的 \(a_i\) 是负数，肯定乘上前 \(i - 1\) 个数当中选 \(j - 1\) 个数乘积的最小值是最优的，但如果只状态转移最大值，就肯定得不到最优解。

分析到这里就很容易写出状态转移了。

状态转移

\[dp1_{i,j} = \begin{cases} \max(dp1_{i-1,j},\ dp2_{i-1,j-1}×a_i), & \text{if }a_i ≤ 0 \\ \max(dp1_{i-1,j},\ dp1_{i-1,j-1}×a_i), & \text{if }a_i > 0 \end{cases} \]

\[dp2_{i,j} = \begin{cases} \max(dp2_{i-1,j},\ dp1_{i-1,j-1}×a_i), & \text{if }a_i ≤ 0 \\ \max(dp2_{i-1,j},\ dp2_{i-1,j-1}×a_i), & \text{if }a_i > 0 \end{cases} \]

此算法时间复杂度为 \(\mathcal{O}(t×5n)\)

最后给出代码

#include 
#define ll long long
using namespace std;
ll n, a[100005];
ll dp1[100005][6], dp2[100005][6];
int main() {
	freopen("maximum.in", "r", stdin);
	freopen("maximum.out", "w", stdout);
	ll t;
	scanf("%lld", &t);
	while (t--) {
		memset(dp1, 128, sizeof(dp1));
		memset(dp2, 127, sizeof(dp2));
		scanf("%lld", &n);
		for (ll i = 1; i <= n; i++) {
			scanf("%lld", &a[i]);
		}
		for (ll i = 0; i <= n; i++) dp1[i][0] = 1, dp2[i][0] = 1;
		for (ll i = 1; i <= n; i++) {
			for (ll j = 1; j <= min(5ll, i); j++) {
				if (a[i] <= 0) dp1[i][j] = max(dp1[i - 1][j], dp2[i - 1][j - 1] * a[i]);
				else dp1[i][j] = max(dp1[i - 1][j], dp1[i - 1][j - 1] * a[i]);
				if (a[i] <= 0) dp2[i][j] = min(dp2[i - 1][j], dp1[i - 1][j - 1] * a[i]);
				else dp2[i][j] = min(dp2[i - 1][j], dp2[i - 1][j - 1] * a[i]);
			}
		}
		printf("%lld\n", dp1[n][5]);
	}
	return 0;
}