题解 | #子数组最大乘积#

子数组最大乘积

http://www.nowcoder.com/practice/9c158345c867466293fc413cff570356

思路

此题是一类动态规划问题，具有重叠子问题和最优子结构的特点，通过找到状态转移方程式来解决问题

方法一：动态规划

我们可以定义一个动态规划数组dp[i]，其表示的是从索引0到索引i位置为止，这一段区间存在的子数组的最大乘积保存在dp[i]中，因此对于一个n长的数组，最终返回结果为max(dp[0]...dp[n])，我们每一次计算dp[i]时候都要在dp[i-1]的基础上进行操作，通过子问题的方式逐步解决问题。
有了这一思路之后，还需要处理正负数的问题。如果仅仅按照上一条的说法，对于数组[-2,3,-4]，对应的dp数组会首先认为dp[0] = -2，之后dp[1] = 3（因为乘3的话只会让最终结果变小，这是不符合最大乘积的规定的），最后dp[3] = 3，这与理论值24是不一致的
问题就在于负数存在于数组中，因此我们需要两个动态规划数组处理该问题。
- 一个为mx数组，专门用于记录最大值
- 一个位mn数组，专门用于记录最小值
状态转移方程列如下（请看下一点解释为什么这样列）：

$图片说明$

这样就很好的解决了第二点中提到的正负问题。第二点种虽然对应的mx[1]仍旧记录为-2，但是mn[1]中记录的就是-6。所以mn数组是间接为mx数组服务的，在mx[2]计算中会取arr[2]*mn[1]的值也就是-4 * -6 = 24，mn的记录是为了那个负号抵消的作用存在的

class Solution {
public:
    double Max(double a, double b, double c, double d) {    // 单独写一个Max函数，因为c++库中max不支持三项比较
        return max(d, max(a, max(b,c)));
    }

    double Min(double a, double b, double c, double d) {    // 同理写一个Min函数
        return min(d, min(a, min(b,c)));
    }

    double maxProduct(vector<double> arr) {
        int n = arr.size();
        if(n == 0) return 0;                                //特殊情况处理
        vector<double> mx(n);
        vector<double> mn(n);
        mx[0] = mn[0] = arr[0];
        for(int i = 1; i < n; i++) {
            mx[i] = Max(arr[i], arr[i]*mx[i-1], arr[i]*mn[i-1], arr[i]);    // 根据转移方程写出最大值转移代码
            mn[i] = Min(arr[i], arr[i]*mx[i-1], arr[i]*mn[i-1], arr[i]);    // 根据转移方程写出最小值转移代码
        }
        return *max_element(mx.begin(), mx.end());                          // 返回mx数组中的最大值才是最终结果
    }
};

复杂度计算

时间复杂度：O(N)，遍历整个数组一遍
空间复杂度：O(N)，维护两个数组

方法二：数学分析(拓展思路，仅限于数据类型为int，本题不适用）

具体思路：

注意：仅限制于数据类型为int类型可以这么操作，原题中是double类型，因此存在0.7这样的数字，乘在一起总乘积出现了反而变小的情况
如果给出的数组中负数的个数为偶数个，则数组中的所有数字全部乘起来就是最大乘积
如果给出的数组中负数的个数为奇数个，则在其中某一个负数处，左右两边的乘积取一个最大值即为这个子数组的最大乘积

class Solution {
public:
    double maxProduct(vector<double> arr) {
        vector<double> rev = arr;            
        reverse(rev.begin(), rev.end());        // 将原序列翻转存储一次
        int n = arr.size();
        for(int i = 1; i < n; i++) {
            arr[i] *= arr[i-1] == 0 ? 1 : arr[i-1];            // 计算正序的累乘结果，分别存在对应的位置
            rev[i] *= rev[i-1] == 0 ? 1 : rev[i-1];            // 计算倒序的累乘结果，分别存在对应的位置
        }
        return max(*max_element(arr.begin(), arr.end()), *max_element(rev.begin(), rev.end()));
    }
};