#P4095. 乘积最大子数组
-
ID: 2332
Tried: 71
Accepted: 32
Difficulty: 7
-
算法标签>动态规划
乘积最大子数组
题目内容
给你一个整数数组nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位整数。
输入描述
一个整数数组nums
输出描述
一个整数表示最大乘积
样例1
输入
2 3 -2 4
输出
6
说明
子数组[2,3]有最大乘积6。
样例2
输入
-2 0 -1
输出
0
说明
结果不能为 2, 因为[−2,−1]不是子数组。
提示：
- 1<=nums.length<=2∗104
- −10<=nums[i]<=10
- nums 的任何子数组的乘积都保证是一个 32-位 整数
题解
题面描述
给定一个整数数组 nums，要求找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积。注意：子数组要求在数组中是连续的一段。测试用例的答案保证为 32-位整数。
思路解析
由于数组中既可能有正数也可能有负数，负数相乘会使得结果变正，同时遇到 0 时会将乘积清零，因此我们需要同时记录当前子数组的最大值和最小值。具体思路如下：
- 定义 dpmax[i] 表示以下标 i 结尾的子数组所能获得的最大乘积；
- 定义 dpmin[i] 表示以下标 i 结尾的子数组所能获得的最小乘积；
- 当遇到负数时，由于负负得正，当前最大值可能由之前的最小值乘以当前值得到；
- 状态转移公式为
- dpmax[i] = max(nums[i], dpmax[i−1] * nums[i], dpmin[i−1] * nums[i])
- dpmin[i] = min(nums[i], dpmax[i−1] * nums[i], dpmin[i−1] * nums[i])
- 同时维护全局最大值即可。
代码分析
-
动态规划思想：
利用两个变量记录当前最大和最小乘积，通过遍历数组不断更新状态。时间复杂度为 O(n)，空间复杂度可以做到 O(1)。 -
负数与 0 的特殊处理：
当遇到负数时，交换当前的最大和最小值；当遇到 0 时，重新初始化最大和最小值为 0 或当前数。 -
边界条件：
初始状态设定为数组的第一个元素，保证子数组非空。
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// 返回数组中乘积最大的连续子数组乘积
int maxProduct(vector<int>& nums) {
// 初始化最大值、最小值以及结果
int curMax = nums[0], curMin = nums[0], res = nums[0];
for (size_t i = 1; i < nums.size(); i++) {
// 当遇到负数时，交换最大值和最小值
if(nums[i] < 0)
swap(curMax, curMin);
// 更新当前最大值和最小值
curMax = max(nums[i], curMax * nums[i]); // 当前最大值 = max(当前数, 前面的最大乘积乘以当前数)
curMin = min(nums[i], curMin * nums[i]); // 当前最小值 = min(当前数, 前面的最小乘积乘以当前数)
// 更新全局最大值
res = max(res, curMax);
}
return res;
}
};
int main(){
// 读取输入
vector<int> nums;
int x;
while(cin >> x) { // 以空格或换行分隔输入
nums.push_back(x);
}
// 调用解法
Solution sol;
int result = sol.maxProduct(nums);
// 输出结果
cout << result;
return 0;
}
Python
class Solution:
# 返回数组中乘积最大的连续子数组乘积
def maxProduct(self, nums: list[int]) -> int:
# 初始化当前最大值、最小值以及结果
cur_max = nums[0]
cur_min = nums[0]
res = nums[0]
# 遍历数组
for num in nums[1:]:
# 当遇到负数时交换当前最大值和最小值
if num < 0:
cur_max, cur_min = cur_min, cur_max
# 更新当前最大值和最小值
cur_max = max(num, cur_max * num) # 当前最大值 = max(当前数, 前面乘积乘以当前数)
cur_min = min(num, cur_min * num) # 当前最小值 = min(当前数, 前面乘积乘以当前数)
# 更新全局最大值
res = max(res, cur_max)
return res
if __name__ == "__main__":
import sys
# 读取输入：以空格或换行分隔数字
nums = list(map(int, sys.stdin.read().split()))
sol = Solution()
print(sol.maxProduct(nums))
Java
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
// 读取输入：以空格或换行分隔数字
while (scanner.hasNextInt()) {
list.add(scanner.nextInt());
}
scanner.close();
int[] nums = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
nums[i] = list.get(i);
}
Solution sol = new Solution();
int result = sol.maxProduct(nums);
System.out.println(result);
}
}
class Solution {
// 返回数组中乘积最大的连续子数组乘积
public int maxProduct(int[] nums) {
// 初始化当前最大值、最小值以及结果
int curMax = nums[0], curMin = nums[0], res = nums[0];
for (int i = 1; i < nums.length; i++) {
// 当遇到负数时交换当前最大值和最小值
if (nums[i] < 0) {
int temp = curMax;
curMax = curMin;
curMin = temp;
}
// 更新当前最大值和最小值
curMax = Math.max(nums[i], curMax * nums[i]); // 当前最大值 = max(当前数, 前面乘积乘以当前数)
curMin = Math.min(nums[i], curMin * nums[i]); // 当前最小值 = min(当前数, 前面乘积乘以当前数)
// 更新全局最大值
res = Math.max(res, curMax);
}
return res;
}
}