首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode: Maximum Product Subarray

Leetcode: Maximum Product Subarray

作者头像
卡尔曼和玻尔兹曼谁曼
发布2019-01-22 17:22:28
3300
发布2019-01-22 17:22:28
举报

题目: 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.

这里的Product是乘积的意思。这道题的tag是Dynamic Programming,所以同样是动态规划的思想,找出局部和全局的递推关系。

思路:这道题和上一道题:Maximum Subarray思路差不多。Maximum Subarray是求子数组和的最大值,这道题是求子数组乘积的最大值。计算最大的乘积同样要考虑负数的情况:一个很小的负数乘以一个负数,可能是一个很大的正数。所以这道题我们要设置两个局部最优变量,一个保存局部最大值,一个保存局部最小值(其实只有当这个局部最小值是负数的时候,才真正起作用)。 它们有如下关系: copyMax = localMax localMax = max(max(localMax * A[i], localMin * A[i]), A[i]) localMin = min(min(copyMax * A[i], localMin * A[i]), A[i]) globalMax = max(localMax, globalMax)

C++代码:

class Solution
{
public:
    int maxProduct(int A[], int n)
    {
        if (n <= 0) return 0;
        int globalMax = A[0];
        int localMax = A[0];
        int localMin = A[0];
        int copyMax = localMax;
        for (int i = 1; i < n; i++)
        {
            copyMax = localMax;
            localMax = max(max(localMax * A[i], localMin * A[i]), A[i]);
            localMin = min(min(copyMax * A[i], localMin * A[i]), A[i]);
            globalMax = max(localMax, globalMax);
        }
        return globalMax;
    }
};

C#代码:

public class Solution
{
    public int MaxProduct(int[] A) 
    {
        if (A.Length <= 0) return 0;
        int globalMax = A[0];
        int localMax = A[0];
        int localMin = A[0];
        int copyMax = localMax;
        for (int i = 1; i < A.Length; i++)
        {
            copyMax = localMax;
            localMax = Math.Max(Math.Max(localMax * A[i], localMin * A[i]), A[i]);
            localMin = Math.Min(Math.Min(copyMax * A[i], localMin * A[i]), A[i]);
            globalMax = Math.Max(globalMax, localMax);
        }
        return globalMax;
    }
}

Python代码:

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxProduct(self, A):
        size = len(A)
        if size <= 0:
            return 0
        globalMax = A[0]
        localMax = A[0]
        localMin = A[0]
        copyMax = localMax
        for i in range(1, size):
            copyMax = localMax
            localMax = max(max(localMax * A[i], localMin * A[i]), A[i])
            localMin = min(min(copyMax * A[i], localMin * A[i]), A[i])
            globalMax = max(globalMax, localMax)
        return globalMax
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015年03月30日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档