我要招人

去企业版

首页 > 试题广场 >

子数组最大乘积

[编程题]子数组最大乘积

热度指数：24199 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个double类型的数组arr，其中的元素可正可负可0，返回连续子数组累乘的最大乘积。

数据范围：数组大小满足 $0 \le n \le 10$ ，数组中元素满足 $|val| \le 10$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例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

算法知识视频讲解

Java

老农爱编程

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)

Java

小灰灰QAQ

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)

Java

LDew

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)

Java

惠灵顿靖

public class Solution {
    public double maxProduct(double[] arr) {
        int n = arr.length;
        //保存最大和最小。动态规划；maxtmp[i]表示以节点i为结尾的连续子数组的最大乘机
        double[] maxtmp=new double[n];
        double[] mintmp=new double[n];
        maxtmp[0] = arr[0];
        mintmp[0] = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > 0) {
                maxtmp[i] = Math.max(arr[i], arr[i] * maxtmp[i-1]);
                mintmp[i] = Math.min(arr[i], arr[i] * mintmp[i-1]);
            } else {
                maxtmp[i] = Math.max(arr[i], arr[i] * mintmp[i-1]);
                mintmp[i] = Math.min(arr[i], arr[i] * maxtmp[i-1]);
            }
        }
        //找出以每个节点为结尾的最大值中的最大值
        double ans=maxtmp[0];
        for(int i=1;i<n;i++){
            ans=maxtmp[i]>ans?maxtmp[i]:ans;
        }
        return ans;
    }
}

发表于 2021-04-13 20:38:07 回复(0)

Java

花落梦里

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)

Java

牛客915296776号

public class Solution {
    public double maxProduct(double[] arr) {
        int n = arr.length;
        double res = arr[0], max = arr[0], min = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > 0) {
                max = Math.max(arr[i], arr[i] * max);
                min = Math.min(arr[i], arr[i] * min);
            } else {
                double pre = max;
                max = Math.max(arr[i], arr[i] * min);
                min = Math.min(arr[i], arr[i] * pre);
            }
            res = Math.max(res, max);
        }
        return res;
    }
}

发表于 2021-02-16 21:44:28 回复(0)

Java

fsSpdTas

大的×正数可能变大小的×正数可能变小

大的×负数可能变小小的×负数可能变大

public class Solution {

public double maxProduct(double[] arr) {
double[][] map=new double[arr.length][2];
double ret;
ret=map[0][0]=map[0][1]=arr[0];//0最小 1最大
for(int i=1;i<arr.length;i++){
double ai=arr[i];
if(ai>0){
map[i][0]=Math.min(ai,ai*map[i-1][0]);
map[i][1]=Math.max(ai,ai*map[i-1][1]);
}else{
map[i][0]=Math.min(ai,ai*map[i-1][1]);
map[i][1]=Math.max(ai,ai*map[i-1][0]);
}
ret=Math.max(ret,map[i][1]);
}
return ret;

}
}

发表于 2020-12-22 21:10:10 回复(0)