博客

乘积最大子数组

题目描述:

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积

。

示例 1:

输入: [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]

输出: 0

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）

链接：

https://leetcode-cn.com/problems/maximum-product-subarray

题解

先将一些闲话吧

这个是我的第一篇题解,才刷leetcode不久,今天才决定写题解.算得上一次进步吧!!比较激动!好了废话不多说开始吧!!

刚才是看到这个题目的时候我就想到与其类似的题目例如最长和的子数列等等!解决这一类问题,其实一开始想到的应该是

动态规划

!

首先我们要确定我们一个思路

1. 让我们在这个数组中寻找一个子数组，使得子数组内的元素的乘积最大。

2. 哪种数会导致我的一个子数组变得最小.

3. 最重要一点来了(如果你不清楚你会疯的)–
   
   那就是当你的数一个最小的负数但是当这个数乘了一个负数(负负得正),就有可能变成最大!
   

所以当你在遍历到

负数

的时候，局部

最小值

和局部

最大值

需要做交换，从而解决负数导致的“颠倒”问题。

既然确定了思路我们就开始准备写出状态转移方程,确认如何写!

状态转移方程



这是基于最长和的子数列相同的思路所得的一个状态转移方程.

所以准备工作已经完毕了!

那么开始进行激动的写代码吧!!(

其实不激动

)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans=-10000000;
        int n=nums.size();
        int max1=1,min1=1,mx,mn;
        for(int i=0;i<n;i++)
       {
           mx=max1;
           mn=min1;
           max1=max(mx*nums[i],max(nums[i],mn*nums[i]));//负负得正
           min1=min(mn*nums[i],min(nums[i],mx*nums[i]));//找最小的负值
           ans=max(max1,ans);
       }
        return ans;
    }
};

时间复杂度： O(n)。

空间复杂度：O(1)。

来自一个大一的小菜鸡!!!

日期

5-18(考试周)哭了!!!