动态规划经典例题：乘积最大连续子数组

题目：

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。例如数组：arr[]={1, 2, 3, -2, 4, -3 } 最大子数组为 {1, 2, 3, -2, 4} 和为8

思路：动态规划

fmax(i) 表示以第 i 个元素结尾的乘积最大子数组的乘积，fmin(i) 表示以第 i 个元素结尾的乘积最小子数组的乘积，这里分为最大和最小是因为数组可能存在负数，最大值乘以负数变成较小值，最小值乘以一个负数也可能变成最大值。

class Solution { public:int maxProduct(vector<int>& nums) {vector <int> maxF(nums), minF(nums);for (int i = 1; i < nums.size(); ++i) {maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i]));}return *max_element(maxF.begin(), maxF.end());} };

直接实现动态方程就可以了，时间复杂度和空间复杂度都是O(n)。由于第 i个状态只和第 i - 1个状态相关，根据[滚动数组]思想，我们可以只用两个变量来维护，这样空间复杂度为O(1)

func maxProduct(nums []int) int {maxF, minF, ans := nums[0], nums[0], nums[0]for i := 1; i < len(nums); i++ {mx, mn := maxF, minFmaxF = max(mx * nums[i], max(nums[i], mn * nums[i]))minF = min(mn * nums[i], min(nums[i], mx * nums[i]))ans = max(maxF, ans)}return ans }func max(x, y int) int {if x > y {return x}return y }func min(x, y int) int {if x < y {return x}return y }

 

 

参考地址：https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
 

总结

以上是生活随笔为你收集整理的动态规划经典例题：乘积最大连续子数组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。