子数组最大乘积

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;
    }
}

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;
    }
}

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

分治算法可解,复杂度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;
}

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;  
}

//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;
}

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))

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;

    }
};

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;
    }
}

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;
    }
};

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;
    }
}

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;
    }
};

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;
    }
};