leetcode 152. Maximum Product Subarray 最大连乘子序列 + 很棒的动态规划DP做法

系统管理员 2022-06-08 06:27 189阅读 0赞

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array \[2,3,-2,4\],  
the contiguous subarray \[2,3\] has the largest product = 6.

题意很简单，这里不就不说了，建议和[leetcode 123. Best Time to Buy and Sell Stock III ][leetcode 123. Best Time to Buy and Sell Stock III] 一起学习。

建议和[leetcode 560. Subarray Sum Equals K 动态规划DP子数组求和][leetcode 560. Subarray Sum Equals K _DP] 和 [leetcode 713. Subarray Product Less Than K 移动窗口][leetcode 713. Subarray Product Less Than K] 一起学习

就是使用DP动态求解，我也没想到是这么做得。

代码如下：

/*
     * 记录当前最大, 最小值. 因为遇到负数时, 与最小值的product可能成为最大值.
     * 
     * */
    public class Solution 
    {
        public int maxProduct(int[] nums) 
        {
            if(nums==null || nums.length<=0)
                return 0;
    
            int maxPro=nums[0] , minPro=nums[0] , maxRes=nums[0];
            for(int i=1;i<nums.length;i++)
            {
                int a = maxPro*nums[i];
                int b = minPro*nums[i];
                maxPro = Math.max(Math.max(a, b), nums[i]);
                minPro = Math.min(Math.min(a, b), nums[i]);
                maxRes = Math.max(maxRes, maxPro);
            }
            return maxRes;
        }
    }

下面是C++的做法，就是做一个动态规划

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int maxProduct(vector<int>& nums) 
        {
            if (nums.size() <= 0)
                return 0;
    
            int maxPro = nums[0], minPro = nums[0], maxRes = nums[0];
            for (int i = 1; i < nums.size(); i++)
            {
                int a = maxPro*nums[i];
                int b = minPro*nums[i];
                maxPro = max(max(a, b),nums[i]);
                minPro = min(min(a, b), nums[i]);
                maxRes = max(maxRes, maxPro);
            }
            return maxRes;
        }
    };

[leetcode 123. Best Time to Buy and Sell Stock III]: http://blog.csdn.net/jackzhang_123/article/details/77988039
[leetcode 560. Subarray Sum Equals K _DP]: http://blog.csdn.net/jackzhang_123/article/details/78832149
[leetcode 713. Subarray Product Less Than K]: http://blog.csdn.net/jackzhang_123/article/details/78884677