首页 > 试题广场 >

子数组最大乘积

[编程题]子数组最大乘积
  • 热度指数:24199 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给定一个double类型的数组arr,其中的元素可正可负可0,返回连续子数组累乘的最大乘积。

数据范围:数组大小满足 ,数组中元素满足
进阶:空间复杂度 ,时间复杂度
示例1

输入

[-2.5,4,0,3,0.5,8,-1]

输出

12.00000

说明

取连续子数组[3,0.5,8]可得累乘的最大乘积为12.00000 
示例2

输入

[1.0,0.0,0.0]

输出

1.00000

说明

取连续子数组[1.0]可得累乘的最大乘积为1.00000 
iMax、iMin分别用来记录以前一个数结尾的子数组的最大乘积、最小乘积。
1. arr[i]>0: iMax = std::max(arr[i], arr[i]*iMax);
2. arr[i]<0: iMax = std::max(arr[i], arr[i]*iMin);    // 相当于是负负得正
所以,当arr[i]<0的时候,交换iMax和iMin即可。
class Solution {
public:
    double maxProduct(vector<double> arr) {
        if(arr.size() == 0) {
            return 0;
        }
        double iMax = 1.0, iMin = 1.0;
        double ans = arr[0];
        for(size_t i = 0; i < arr.size(); i++) {
            if(arr[i] < 0) {
                std::swap(iMax, iMin);
            }
            iMax = std::max(arr[i], iMax*arr[i]);
            iMin = std::min(arr[i], iMin*arr[i]);
            ans = std::max(iMax, ans);
        }
        return ans;
    }
};


发表于 2020-09-18 11:38:06 回复(1)
public class Solution {
    //连续子数组乘积的最大值
    public double maxProduct(double[] arr) {
        double min=arr[0];
        double max=arr[0];
        double res=arr[0];
        //最大值有可能出现在之前的最小值*当前值,比如最小值为-100,arr[i]<0,同理,最小值也可能出现在之前的最大值,所以每次比较三个值
        for(int i=1;i<arr.length;i++){
            double last_max=max,last_min=min;
            min=Math.min(arr[i],Math.min(arr[i]*last_min,arr[i]*last_max));
            max=Math.max(arr[i],Math.max(arr[i]*last_min,arr[i]*last_max));
            res=Math.max(max,res);
        }
        return res;
    }
}

发表于 2021-03-27 11:08:53 回复(0)
public class Solution {
      public double maxProduct(double[] arr) {
        double[] mx = new double[arr.length];
        double[] mi = new double[arr.length];
        mx[0] = arr[0];
        mi[0] = arr[0];
        double res = arr[0];
        for (int i = 1; i < arr.length; i++) {
            mx[i] = Double.max(arr[i], Double.max(mi[i - 1] * arr[i], mx[i - 1] * arr[i]));
            mi[i] = Double.min(arr[i], Double.min(mi[i - 1] * arr[i], mx[i - 1] * arr[i]));
            if (res < mx[i])
                res = mx[i];
        }
        return res;
    }
}

发表于 2021-11-29 10:20:45 回复(0)
class Solution:
    def maxProduct(self , arr ):
        maxi, mini, maxproduct = 1, 1, arr[0]
        for i in range(len(arr)):
            maxi, mini = max(maxi * arr[i], mini * arr[i], arr[i]), min(maxi * arr[i], mini * arr[i], arr[i])
            maxproduct = max(maxi, maxproduct)
        return maxproduct

发表于 2021-06-01 00:16:52 回复(0)
因为数组的值可正可负可0,所以需要用两个变量:curmax、curmin,分别保存以当前遍历到的arr[i]为结尾时,子数组所能得到的最大值和最小值。
(因为最小值可能为负,这时候如果遇到下一个为负的数,负负得正,乘积可能变成最大的)
class Solution {
public:
    double maxProduct(vector<double> arr) {
        int len=arr.size();
        double curmax=arr[0];
        double curmin=arr[0];
        double maxnum=curmax;
        for(int i=1;i<len;i++) {
            double a=arr[i]*curmax;
            double b=arr[i]*curmin;
            if(a>b) {
                curmax=max(a,arr[i]); //以该位置作为尾结点时可能获得的最大值
                curmin=min(b,arr[i]); //以该位置作为尾点时可能获得的最小值
            } else{
                curmax=max(b,arr[i]); 
                curmin=min(a,arr[i]);
            }
            maxnum=max(curmax,maxnum);
        }
        return maxnum;
    }
};


发表于 2021-04-05 11:14:47 回复(0)
分治算法可解,复杂度O(n*logn)

分治过程:问题划分->求解子问题->合并问题的解。

1.本题分治思路:[L,R]区间上的最大值出现的情况只有3种:
    1)在左半区间出现;
    2)在右半区间出现;
    3)横跨左右半区间出现。
    计算以上3种情况的值,返回其中最大值就是最终结果。 

2.分治算法的时间复杂度为什么是O(n*logn)?——每次都将区间完美二分,递归过程是一颗二叉树
    (1)对于区间[L,R],分割点选取mid=(L+R)>>1,即区间的二分点;
    (2)对于长n的区间,最多二分log(n)次:
        每次都二分区间,相当于区间长度每次都除以2,最终区间长度为1时停止划分区间:
        其中 n/(2^k)=1,2^k=n => k=log(n),
        即对于长n的区间最多分割log(n)次,也就是分治递归深度最大为log(n)。    
     (3)计算第3种情况,需要遍历一遍区间,复杂度O(n):
        1)第1层区间[1,n],求解第3种情况的解需遍历一遍区间,复杂度O(n);
        2)第2层从第一层划分出两个区间:[1,n/2]和[n/2+1,n],每个子区间求解第3种情况
        都要遍历一遍子区间,第二层总复杂度=O(n/2+n/2)=O(n);
        3)第3层从第2层划分出4个区间,每个区间长度n/4,复杂度=O(n/4+n/4+n/4+n/4)=O(n);
        4)依次类推,每一层都把该层所有的子区间遍历一遍,子区间总长度为n,复杂度O(n)。
    (4)每层都要遍历一遍区间,所以总复杂度为:O(递归层数*每层区间长度)=O(log(n)*n)
//代码
public double maxProduct(double[] arr) {
    return dfs(arr,0,arr.length-1);
}
//返回区间[l,r]上的最大子数组累乘值
private double dfs(double[] arr,int l,int r){
    if(r<l) return 0;
    if(l==r) return arr[l];
    double ans=0;
    int mid=(l+r)>>>1;
    double L=dfs(arr,l,mid);//递归计算左半区间最大值
    double R=dfs(arr,mid+1,r);//递归计算右半区间最大值
    ans=Math.max(L,R);//比较左右子区间的最大值
    //计算横跨两个区间的最大值,复杂度O(n).注意处理同负的情况
    double maxL=0,minL=0,mulL=1,maxR=0,minR=0,mulR=1;
    for(int i=mid;i>=l;i--){//计算分割点左边最大值
        mulL*=arr[i];
        maxL=Math.max(maxL,mulL);//最大正值
        minL=Math.min(minL,mulL);//最大负值
    }
    for(int i=mid+1;i<=r;i++){//计算分割点右边最大值
        mulR*=arr[i];
        maxR=Math.max(maxR,mulR);
        minR=Math.min(minR,mulR);
    }
    ans=Math.max(ans,minL*minR);//注意处理同负的情况
    ans=Math.max(ans,maxL*maxR);
    return ans;
}

编辑于 2021-04-05 09:08:49 回复(1)
js版本 累计的乘积
function maxProduct( arr ) {
    // write code here
    // 如果数组里面有0或者负数的情况,会影响到数的大小
    let min = arr[0];
    let max = min;//一开始的数
    let res = max;
    for(let i=1;i<arr.length;i++){
        let last_max = max,last_min = min;
        min = Math.min(arr[i],arr[i]*last_min,arr[i]*last_max);//最小的数肯定是从这几个地方来的
        max = Math.max(arr[i],arr[i]*last_max,arr[i]*last_min);
        res = Math.max(res,max)
    }
    return res;  
}

发表于 2020-08-31 15:36:39 回复(0)
public class Solution {
    public double maxProduct(double[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
        
        double currentMax = arr[0];
        double currentMin = arr[0];
        double max = arr[0];
        
        for(int i = 1; i < arr.length; i++){
            // 存储前一个循环计算的最大值用于计算当前最小值即可
            double preMax = currentMax;
            currentMax = Math.max(Math.max(preMax * arr[i], currentMin * arr[i]), arr[i]);
            currentMin = Math.min(Math.min(preMax * arr[i], currentMin * arr[i]), arr[i]);
            max = Math.max(max, currentMax);
        }
        
        return max;
    }
}
发表于 2020-04-25 00:51:43 回复(2)
//leetcode中的Maximum Product Subarray问题
//https://leetcode.com/problems/maximum-product-subarray/

public double maxProduct(double[] arr) {
    if(arr.length == 0)
        return 0;
        
    double maxpre = arr[0];
    double minpre = arr[0];
    double max = arr[0];
        
    double maxhere, minhere;
        
    for(int i=1; i<arr.length; i++){
        maxhere = Math.max(Math.max(maxpre*arr[i], minpre*arr[i]), arr[i]);
        minhere = Math.min(Math.min(maxpre*arr[i], minpre*arr[i]), arr[i]);
        max = Math.max(max, maxhere);
        maxpre = maxhere;
        minpre = minhere;
    }
    return max;
}

发表于 2015-09-01 21:26:36 回复(0)
class Solution:
    def maxProduct(self , nums: List[float]) -> float:
        # write code here
        dp_max=[1]*len(nums)
        dp_max[0]=nums[0]
        dp_min=[1]*len(nums)
        dp_min[0]=nums[0]
        for i in range(1,len(nums)):
            dp_max[i]=max(nums[i],dp_min[i-1]*nums[i],dp_max[i-1]*nums[i])
            dp_min[i]=min(nums[i],dp_max[i-1]*nums[i],dp_min[i-1]*nums[i])
        return max(max(dp_max),max(dp_min))

发表于 2022-01-22 06:19:46 回复(0)
class Solution {
public:
    double maxProduct(vector<double> arr) {
        int n = arr.size();
        double ans =0.0;
        vector<vector<double>> dp(2, vector<double> (n,0));
        dp[0][0]=arr[0],dp[1][0]=arr[0];
        ans =arr[0];
        for(int i=1;i<n;i++){
            dp[0][i] = max(max(dp[0][i-1]*arr[i],dp[1][i-1]*arr[i]),arr[i]);
            dp[1][i] = min(min(dp[0][i-1]*arr[i],dp[1][i-1]*arr[i]),arr[i]);
            if(ans<dp[0][i]){
                ans = dp[0][i];
            }
        }
        return ans;

    }
};

发表于 2022-09-14 09:11:25 回复(0)
class Solution:
    def maxProduct(self , arr: List[float]) -> float:
        # write code here
        save = []
        if(len(arr) == 0):
            return 0
        else:
            save.append([arr[0],arr[0]])
            for i in range(1,len(arr)):
                if(arr[i]!=0):
                    if(arr[i]>0):
                        t1 = min(save[-1][0]*arr[i],arr[i])
                        t2 = max(arr[i],save[-1][1]*arr[i])
                        save.append([t1,t2])
                    elif(arr[i]<0):
                        t1 = min(save[-1][1]*arr[i],arr[i])
                        t2 = max(arr[i],save[-1][0]*arr[i])
                        save.append([t1,t2])
                     #and save[-1][0] and save[-1][1]
                else:
                    save.append([0,0])
        #print(save)
        return max([i[1] for i in save])
发表于 2022-01-30 15:27:00 回复(0)
public class Solution {
    public double maxProduct(double[] arr) {
        double max = 0.0 ;
        double dp[][] = new double[arr.length][arr.length]; //为了存放最大值
        if(arr.length == 1){
            return arr[0];
        }
        int j = 0;
        for(int i = 0 ; i < arr.length; i ++){
            dp[i][i] = arr[i];
            double sum = arr[i];//为了进行累乘
            for(j = i + 1 ; j < arr.length; j ++){
                if(arr[j] == 0){
                    dp[i][j] = Math.max(dp[i][j - 1],0);
                    j = j + 1;//这里是因为,如果不多加一次,那么直接跳出循环,就会到
                              //22行,此时22行减 了1.
                    break;
                }
                sum = sum * arr[j];
                dp[i][j] = Math.max(dp[i][j - 1],sum);
            }
            max = Math.max(max,dp[i][j - 1]);//由于考虑到如果是全部不为0的情况下,那么j一定会多加1,
                                             //所以减掉1
        }
        return max;
    }
}

发表于 2022-01-15 17:33:05 回复(0)
class Solution {
public:
    double maxProduct(vector<double> arr) {
        if(arr.empty()) return 0;
        double res = arr[0];
        double imax = 1.0, imin = 1.0;
        for(int i=0;i<arr.size();++i){
            if(arr[i]==0){
                imax = 1.0;
                imin = 1.0;
                continue;
            }
             //注意不要先更新imax
            double temp = max(arr[i], max(arr[i]*imax, arr[i]*imin)); 
            imin = min(arr[i], min(arr[i]*imax, arr[i]*imin));
            imax = temp;
            res = max(res, imax);
        }
        return res;
    }
};

发表于 2021-12-25 01:21:36 回复(0)
# python 用字段处理,没用二维数组;
# 理解思路:for i 这里从前往后处理(包含了截取掉前面某一段的逻辑),字典保留每个子串的最大、最小值
class Solution:
    def maxProduct(self , arr: List[float]) -> float:
        if arr is None:
            return 0
        if len(arr) == 1:
            return arr[0]
        
        max_value = {0: arr[0]}
        min_value = {0: arr[0]}

        for i in range(1, len(arr)):
            max_value_tmp = max(max_value.get(i-1) * arr[i], min_value.get(i-1) * arr[i], arr[i])
            min_value_tmp = min(max_value.get(i-1) * arr[i], min_value.get(i-1) * arr[i], arr[i])
            max_value.update({i: max_value_tmp})
            min_value.update({i: min_value_tmp})
        max_list = [x for x in max_value.values()]
        max_list.sort()
        return max_list[-1]
发表于 2021-12-02 10:54:33 回复(0)
public class Solution {
    public double maxProduct(double[] arr) {
        int n = arr.length;
        double mi[] = new double[n + 1];
        double ma[] = new double[n + 1];
        ma[0] = 1;
        mi[0] = 1;
        double res = -10101;
        for(int i = 1;i <= n;i++){
            ma[i] = Math.max(arr[i - 1],arr[i - 1] * ma[i - 1]);
            ma[i] = Math.max(ma[i],arr[i - 1] * mi[i - 1]);
            mi[i] = Math.min(arr[i - 1],mi[i - 1] * arr[i - 1]);
            mi[i] = Math.min(mi[i],arr[i - 1] * ma[i - 1]);
            res = Math.max(ma[i],res);
        }
        return res;
    }
}

发表于 2021-11-19 10:45:48 回复(0)
class Solution:
    def maxProduct(self , arr ):
        # write code here
        max=arr[0]
        l=len(arr)
        for i in range(l):
            max_temp=arr[i]
            val=arr[i]
            for j in range(i+1,l):
                val=val*arr[j]
                if val > max_temp:
                    max_temp=val
            if max<max_temp:
                max=max_temp
        return max
发表于 2021-10-09 14:36:44 回复(0)
class Solution {
public:
    double maxProduct(vector<double> arr) {
        if(arr.size() == 1) return arr[0];
        double sum = INT_MIN;
        vector<vector<double>> dp(arr.size() + 1,(vector<double>(arr.size() + 1,0)));
        dp[0][0] = 0;
        for(int i = 1; i < arr.size() + 1; i++) dp[i][0] = arr[i - 1];
        for(int i = 1; i < arr.size() + 1; i++) dp[0][i] = arr[i - 1];
        for(int i = 1; i < arr.size() + 1; i++){
            for(int j = i; j < arr.size() + 1; j++){
                if(i == j) dp[i][j] = dp[0][j];
                else {
                    dp[i][j] = dp[i][j - 1] * dp[0][j];
                }
            }
        }
        for(int i = 0; i < arr.size() + 1; i++){
            for(int j = 0; j < arr.size() + 1; j++){
                sum = max(sum,dp[i][j]);
            }
        }
        return sum;
    }
};

wo shi *****
发表于 2021-09-20 15:12:19 回复(0)
class Solution {
public:
    double maxProduct(vector<double> arr) {
        int n=arr.size();
        double MaxNum=arr[0];
        double MinNum=arr[0];
        double ans=arr[0];
        //最小值也可能变成最大值
        //最大值也可能变成最小值
        //所以需要维护两个变量
        for(int i=1;i<n;i++){
            double tmpMax=MaxNum,tmpMin=MinNum;
            MaxNum=max(tmpMax*arr[i],max(tmpMin*arr[i],arr[i]));
            MinNum=min(tmpMin*arr[i],min(tmpMax*arr[i],arr[i]));
            ans=max(ans,MaxNum);
        }
        return ans;
    }
};

发表于 2021-09-11 11:13:31 回复(0)
class Solution {
public:
    double maxProduct(vector<double> arr) {
        vector<vector<double>> dp(2,vector<double>(arr.size(),0));
        double res=arr[0];
        if(arr[0]>0)    dp[0][0] = arr[0];
        else    dp[1][0] = arr[0];
        for(int i=1;i<arr.size();i++){
            if(arr[i]>0){
                dp[0][i] = max(dp[0][i-1]*arr[i],arr[i]);
                dp[1][i] = dp[1][i-1]*arr[i];
            }else{
                dp[0][i] = dp[1][i-1]*arr[i];
                dp[1][i] = min(dp[0][i-1]*arr[i],arr[i]);
            }
            res = max(res,dp[0][i]);
        }
        return res;
    }
};
发表于 2021-09-05 11:12:45 回复(0)