Maximum Product Subarray 求最大子数组乘积

水深无声 2022-10-02 01:53 186阅读 0赞

Given an integer array `nums`, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
    Output: 6
    Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
    Output: 0
    Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

以下摘自OJ官方解答，大体思路相同，写法简洁：

Besides keeping track of the largest product, we also need to keep track of the smallest product. Why? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number.

Let us denote that:

f(k) = Largest product subarray, from index 0 up to k.

Similarly,

g(k) = Smallest product subarray, from index 0 up to k.

Then,

f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
    g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )

There we have a dynamic programming formula. Using two arrays of size *n*, we could deduce the final answer as f(*n*\-1). Since we only need to access its previous elements at each step, two variables are sufficient.

public int maxProduct(int[] A) {
       assert A.length > 0;
       int max = A[0], min = A[0], maxAns = A[0];
       for (int i = 1; i < A.length; i++) {
          int mx = max, mn = min;
          max = Math.max(Math.max(A[i], mx * A[i]), mn * A[i]);
          min = Math.min(Math.min(A[i], mx * A[i]), mn * A[i]);
          maxAns = Math.max(max, maxAns);
       }
       return maxAns;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关乘积最大子数组

乘积最大子数组 1、参考资料 https://leetcode-cn.com/problems/maximum-product-subarray/ 2、题目要求

柔情只为你懂/ 2022年12月08日 01:47/ 0 赞/ 348 阅读

相关 Maximum Product Subarray 求最大子数组乘积

Given an integer array `nums`, find the contiguous subarray within an array (containing

水深无声/ 2022年10月02日 01:53/ 0 赞/ 187 阅读

相关 leetcode 152. Maximum Product Subarray | 152. 乘积最大子数组（Java）

题目 [https://leetcode.com/problems/maximum-product-subarray/][https_leetcode.com_probl

亦凉/ 2022年09月04日 09:51/ 0 赞/ 212 阅读

相关 Maximum Product Subarray（C++乘积最大子数组）

（1）遍历 class Solution { public: int maxProduct(vector<int>& nums) {

女爷i/ 2022年08月30日 05:29/ 0 赞/ 141 阅读

相关子数组最大乘积

给定一个double类型的数组arr，其中的元素可正可负可0，返回子数组累乘的最大乘积。例如arr=\[-2.5，4，0，3，0.5，8，-1\]，子数组\[3，0.5，8\]

不念不忘少年蓝@/ 2022年08月18日 02:15/ 0 赞/ 211 阅读

相关 Maximum Product Subarray--LeetCode

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

柔情只为你懂/ 2022年08月07日 13:35/ 0 赞/ 188 阅读

相关 Maximum Subarray(最大子序列和)

给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5

喜欢ヅ旅行/ 2022年05月12日 01:24/ 0 赞/ 170 阅读

相关 LeetCode 152.Maximum Product Subarray (乘积最大子序列)

题目描述：给定一个整数数组 `nums` ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。示例 1: 输入: [2,3,-2,4] 输出

喜欢ヅ旅行/ 2022年05月08日 19:48/ 0 赞/ 217 阅读

相关 LeetCode：152. Maximum Product Subarray（最大的乘积数组）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

落日映苍穹つ/ 2022年04月10日 03:45/ 0 赞/ 221 阅读

相关 LeetCode : 152. Maximum Product Subarray 最大乘积子数组

试题： Given an integer array nums, find the contiguous subarray within an array (contain

绝地灬酷狼/ 2021年06月24日 16:10/ 0 赞/ 440 阅读