首页 > 试题广场 >

连续子数组的最大乘积

[编程题]连续子数组的最大乘积
  • 热度指数：5576 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一个长度为n的整型数组nums，数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。
1.子数组是连续的，且最小长度为1，最大长度为n
2.长度为1的子数组，乘积视为其本身，比如[4]的乘积为4
3.该题的数据保证最大的乘积不会超过int的范围，即不超过
数据范围:



示例1

输入

[3,2,-1,4]

输出

6

说明

子数组[3,2]的乘积为6，[3,2,-1,4]的乘积为-24，[4]的乘积为4，故返回6
示例2

输入

[-3,0,-2]

输出

0

说明

因为0在中间，所有包含0的子数组的乘积都为0，另外的数都是负数，所以最大乘积的子数组为[0]，返回为0，因为子数组要求是连续的，所以[-3,-2]不是[-3,0,-2]的子数组，所以不能为6，
示例3

输入

[-3,2,-2]

输出

12
算法知识视频讲解
添加回答
Java
小灰灰QAQ头像 小灰灰QAQ 
 //max是以i结尾的最大乘积  min是以i结尾的最小乘积
     public static int maxProduct(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        int result =  nums[0];
        for (int i = 1; i < nums.length; i++) {
            int t =max;
            max = Math.max(nums[i], Math.max(max * nums[i], min * nums[i]));
            min = Math.min(nums[i], Math.min(t * nums[i], min * nums[i]));
            result = Math.max(result,max);
        }
        return result;
    }

发表于 2022-02-17 14:27:34 回复(0)
唐氏综合征头像 唐氏综合征
脑溢血解法：OOM 
  public static int maxProduct(int[] nums) {
        // write code here
        int len = nums.length;
        if (len == 1)
            return nums[0];
        // 表示 i 到 j 的最大乘积, i > j
        int[][] dp = new int[len + 1][len + 1];

        // 初始化第一行
        dp[1][1] = nums[0];
        int res = nums[0];
        for (int i = 2; i <= len; i++) {
            dp[1][i] = dp[1][i - 1] * nums[i - 1];
            res = Math.max(res, dp[1][i]);
        }

        // 开始动态规划计算 i 到 j 的连续数组的最大乘积
        for (int i = 2; i <= len; i++) {
            for (int j = i; j <= len; j++) {
                if (i == j){
                    dp[i][j] = nums[i - 1];
                    res = Math.max(res, dp[i][j]);
                }
                else if (i < j) {
                    dp[i][j] = dp[i][j - 1] * nums[j - 1];
                    res = Math.max(res, dp[i][j]);
                }

            }
        }

        return res;
    }
正确解法： 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public static int maxProduct(int[] nums) {
        int len = nums.length;
        if (len == 1)
            return nums[0];

        int[] maxDp = new int[len];
        int[] minDp = new int[len];
        maxDp[0] = nums[0];
        minDp[0] = nums[0];
        int res = nums[0];

        for (int i = 1; i < len; i++) {
            // 1. nums[i] 本身也是一个子序列
            // 2. 最大值乘以当前值可能为最大值（当前为正）
            // 3. 最小值乘以当前值可能为最大值（当前为负）
            maxDp[i] = Math.max(nums[i], Math.max(maxDp[i - 1] * nums[i],
                                                  minDp[i - 1] * nums[i]));
            minDp[i] = Math.min(nums[i], Math.min(maxDp[i - 1] * nums[i],
                                                  minDp[i - 1] * nums[i]));
            res = Math.max(res, maxDp[i]);
        }

        return res;
    }
}



发表于 2024-04-29 23:14:45 回复(1)
Java
MChen-67头像 MChen-67 
// 从左往右一直累乘，记录最大值，遇到0后从1开始。同样的方式可以从右往左进行。
public int maxProduct (int[] nums) {
    long res = nums[0];
    long m = 1;
    for (int i = 0; i < nums.length; i++) {
        m = m * nums[i];
        res = Math.max(res, m);
        if (m == 0) {
            m = 1;
        }
    }
    m = 1;
    for (int i = nums.length - 1; i >= 0; i--) {
        m = m * nums[i];
        res = Math.max(res, m);
        if (m == 0) {
            m = 1;
        }
    }
    return (int)res;
}
时间复杂度:O(n) 空间复杂度 O(1)
发表于 2022-05-04 10:27:16 回复(0)
礼堂纯真丁一郎头像 礼堂纯真丁一郎 
public int maxProduct (int[] nums) {
        // write code here
        if (nums.length < 2) return nums[0];
        int res = nums[0];
        int dp = 1;
        for (int i = 0; i < nums.length; i++) {
            dp = dp * nums[i];
            res = Math.max(res, dp);
            if (dp == 0) {
                dp = 1;
            }
        }
        //先正序遍历一遍，此时会出现如果两个连续负数导致结果遗漏问题
        //例如6，9，-3，-7，8，0，-1，6
        //所以再逆序遍历一遍进行结果检查
        dp = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            dp = dp * nums[i];
            res = Math.max(res, dp);
            if (dp == 0) {
                dp = 1;
            }
        }
        return res;
    }

发表于 2024-04-15 14:32:04 回复(0)
C#
苦行潜修者头像 苦行潜修者
using System;
using System.Collections.Generic;

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int maxProduct (List<int> nums) {
        // write code here
        if (nums == null || nums.Count == 0)
            return 0;
        List<int> lsF = new List<int>() {
            nums[0]
        };
        List<int> ls = new List<int>() { };
        int nMaxMult = lsF[0];
        for (int i = 1; i < nums.Count; i++) {
            ls.Clear();
            ls.Add(nums[i]);
            nMaxMult = nMaxMult > nums[i] ? nMaxMult : nums[i];
            for (int j = 0; j < lsF.Count; j++) {
                int nVal = nums[i] * lsF[j];
                if (ls.IndexOf(nVal) < 0)
                    ls.Add(nVal);
                nMaxMult = nMaxMult > nVal ? nMaxMult : nVal;
            }
            lsF.Clear();
            lsF.AddRange(ls);
        }
        return nMaxMult;
    }
}
编辑于 2024-03-29 17:38:25 回复(0)
Java
牛客839384289号头像 牛客839384289号 
public int maxProduct (int[] nums) {
    // write code here
    int len=nums.length ,res=nums[0];
    int[] maxArr=new int[len] ,minArr=new int[len];
    maxArr[0]=nums[0];
    minArr[0]=nums[0];
    for(int i=1;i<len;i++){
        maxArr[i]=Math.max(Math.max(nums[i] ,maxArr[i-1]*nums[i]) ,minArr[i-1]*nums[i]);
        minArr[i]=Math.min(Math.min(nums[i] ,maxArr[i-1]*nums[i]) ,minArr[i-1]*nums[i]);
        res=Math.max(maxArr[i] ,res);
    }
    return res;
}

编辑于 2024-03-10 16:11:13 回复(0)
牛客2024007号头像 牛客2024007号 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int maxProduct (int[] nums) {
        // write code here
        // dp[i] 数组0 - i的以i结尾的子数组的最大乘积,但是dp[i]既有可能从max转移过来，也有可能从最小的负数转移过来
        int len = nums.length;
        int[] dpMax = new int[len];
        int[] dpMin = new int[len];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int max = nums[0];
        for(int i = 1; i < len; i++) {
            dpMax[i] = Math.max(nums[i], Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
            dpMin[i] = Math.min(nums[i], Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
            max = Math.max(dpMax[i], max);
        }
        return max;
    }
}

编辑于 2024-01-30 20:52:47 回复(0)
C++
一品统合头像 一品统合
  • 当前元素为0，那么以当前元素结尾的子数组的最大乘积为0，即元素本身。
  • 当前元素不为0，累乘到当前元素，依据之前累乘结果、当前元素的符号不同，区分最大值、最小值。
  •  （1）之前累乘结果，当前元素符号相同，乘积为正，是较大值。但是若下一个元素为负，那么该结果乘负元素就是负值，不再是最大值候选。
  • （2）之前累乘结果，当前元素符号不同，乘积为负，是较小值。但是若下一个元素为负，那么该结果乘负元素就是正值，可能成为最大值候选。
  • 因此需要记录前一元素处累乘结果的最大、最小值，乘当前元素后区分出新的最大、最小值。 
class Solution {
public:
    /**
     * 当前元素为0，那么以当前元素结尾的子数组的最大乘积为0，即本身。
     * 当前元素不为0，累乘到当前元素可能为正，也可能为负，也可能是
     * 当前元素本身。
     * 记录累乘最大值、最小值然后递推下一个元素，并使用
     * 变量维护已知的最大乘积。
     */
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        int pre_pos = 1;
        int pre_neg = 1;
        for (int i = 0; i < nums.size(); i++) {
            pre_pos *= nums[i];
            pre_neg *= nums[i];
            int temp = max(nums[i], max(pre_pos, pre_neg));
            pre_neg = min(nums[i], min(pre_pos, pre_neg));
            pre_pos = temp;
            res = max(res, pre_pos);
        }
        return res;
    }
};


发表于 2023-05-31 23:21:53 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func maxProduct( nums []int ) int {
    pre1,pre2,ans:=nums[0],nums[0],nums[0]
    for _,x:=range nums[1:]{
        tmp:=pre1
        pre1=max(max(pre1*x,pre2*x),x)
        pre2=min(min(tmp*x,pre2*x),x)
        if pre1>ans{
            ans=pre1
        }
    }
    return ans
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}

发表于 2023-03-11 19:30:35 回复(0)
重庆大厦卖咖喱头像 重庆大厦卖咖喱 
class Solution {
    public int maxProduct(int[] nums) {
        if (nums ==null || nums.length==0)  return 0;
        int res=nums[0];
        int pre_max=nums[0];
        int pre_min=nums[0];
        for (int i=1;i<nums.length;i++){
            int cur_max=Math.max(Math.max(pre_max*nums[i],pre_min*nums[i]),nums[i]);
            int cur_min=Math.min(Math.min(pre_max*nums[i],pre_min*nums[i]),nums[i]);
            res=Math.max(res,cur_max);
            pre_max=cur_max;
            pre_min=cur_min;
        }
        return res;
    }
}


发表于 2023-02-28 04:30:24 回复(0)
Python2
菜鸡升职记头像 菜鸡升职记 
# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/abbec6a3779940aab2cc564b22d36859?tpId=196&tqId=37119&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        设maxDp[i]表示以nums[i]结尾的连续子数组的乘积的最大值，minDp[i]表示以nums[i]结尾的连续子数组乘积的最小值
        初始化：
            maxDp[0] = nums[0]
            minDp[0] = nums[0]
        状态转移方程：
            maxDp[i] = max(nums[i], nums[i] * maxDp[i-1], nums[i] * minDp[i-1])
            minDp[i] = min(nums[i], nums[i] * minDp[i-1], nums[i] * maxDp[i-1])
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n)
    """

    def maxProduct(self, nums):
        # write code here
        n = len(nums)

        maxDp, minDp = [0] * n, [0] * n

        maxDp[0], minDp[0], res = nums[0], nums[0], nums[0]
        for i in range(1, n):
            maxDp[i] = max(nums[i], nums[i] * maxDp[i - 1], nums[i] * minDp[i - 1])
            minDp[i] = min(nums[i], nums[i] * minDp[i - 1], nums[i] * maxDp[i - 1])
            res = max(res, maxDp[i])

        # print maxDp, minDp
        return res


if __name__ == "__main__":
    sol = Solution()

    # nums = [3, 2, -1, 4]

    # nums = [-3, 0, -2]

    nums = [-3, 2, -2]

    res = sol.maxProduct(nums)

    print res

发表于 2022-07-03 10:08:05 回复(0)
Python 3
Nacylin头像 Nacylin
发表于 2022-06-23 09:38:45 回复(0)
饥饿的懒羊羊在刷题头像 饥饿的懒羊羊在刷题
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int maxProduct (int[] nums) {
        // write code here
        int max_value=nums[0],min_value=nums[0];
        int result=nums[0];
        for(int i=1;i<nums.length;i++){
            //负值的时候交换大小
            if(nums[i]<0){
                int temp=max_value;
                max_value=min_value;
                min_value=temp;
            }
            max_value=Math.max(nums[i],max_value*nums[i]);
            min_value=Math.min(nums[i],min_value*nums[i]);
            
            result=Math.max(result,max_value);
        }
        return result;
    }
}
发表于 2022-05-05 20:13:22 回复(0)
C++
Acmen_沉梦昂志头像 Acmen_沉梦昂志 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxProduct(vector<int>& nums) {
        // write code here
        int n = nums.size();
        vector<int> dpmax(n + 1, INT_MIN) ,dpmin(n + 1,INT_MAX);
        dpmax[1] = nums[0];
        dpmin[1] = nums[0];
        int res= nums[0];
        for(int i = 2;i <= n;i++){
            if (nums[i-1] > 0){
                dpmin[i] = min(dpmin[i-1] * nums[i-1],nums[i-1]);
                dpmax[i] = max(dpmax[i-1] * nums[i-1],nums[i-1]);
            }
            else{
                dpmax[i] = max(dpmin[i-1] * nums[i-1],nums[i-1]);
                dpmin[i] = min(dpmax[i-1] * nums[i-1],nums[i-1]);
            }
            res = max(res,dpmax[i]);
        }
        return res;
    }
};
设置两个dp数组即可
发表于 2022-02-16 20:28:07 回复(0)
Python 3
牛客343459580号头像 牛客343459580号
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def maxProduct(self , nums: List[int]) -> int:
        # write code here
        save = [[nums[0],nums[0]]]
        for i in range(1,len(nums)):
            if(nums[i] > 0):
                min_v = save[-1][0]*nums[i]
                max_v = max(nums[i]*save[-1][1],nums[i])
                save.append([min_v,max_v])
            elif(nums[i] < 0):
                min_v = min(nums[i]*save[-1][1],nums[i])
                max_v = save[-1][0]*nums[i]
                save.append([min_v,max_v])
            else:
                save.append([0,0])
               #< save[]nums[i]):
        return max([i[1] for i in save])
发表于 2022-02-15 18:46:46 回复(0)
提交观点

问题信息

动态规划
上传者：牛客301499号
难度：
15条回答 1583浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号