Xing's Techlog

连续子数组最大累乘积

Posted on Edited on In

求连续子数组的最大乘积。相关题目：Leetcode 152. Maximum Product Subarray

题目：给定一个double类型的数组arr，其中的元素可正、可负、可0，返回子数组的最大乘积。如 arr=[-2.5, 4, 0, 3, 0.5, 8, -1]，子数组[3, 0.5, 8]累乘积可以获得最大值12.

算法：动态规划

设以arr[i-1]结尾的最小累成积min，以a[i-1]结尾的最大累成积为max，那么以arr[i]结尾的最大累乘积只有以下三种可能：

  1. max(arr[1]) * arr[2]，如[3, 4, 5]
  2. min(arr[1]) * arr[2]，如[-2, 3, -4]
  3. arr[2]，如[0.1 ,0.1, 100]

这三种结果中最大的就作为以arr[i]的最大累乘积，最小的作为arr[i]的最小累乘机，然后再计算arr[i+1]。

结果 = Max{以arr[0]结尾的所有子数组的最大累乘积, 以arr[1]结尾的所有子数组的最大累乘积, … , 以arr[arr.length - 1]结尾的所有子数组的最大累乘积}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double maxProduct(double[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    double max = arr[0];
    double min = arr[0];
    double res = arr[0];
    double maxEnd = 0;
    double minEnd = 0;
    for (int i = 1; i < arr.length; ++i) {
        maxEnd = max * arr[i];
        minEnd = min * arr[i];
        max = Math.max(Math.max(maxEnd, minEnd), arr[i]);
        min = Math.min(Math.min(maxEnd, minEnd), arr[i]);
        res = Math.max(res, max);
    }
    return res;
}
Related Posts