动态规划：n-1个数的组合中最大乘积组 解题思路

上一篇文章讲了快速排序，这期讲讲对动态规划的理解：
动态规划的思想是 将问题划分为多个子问题，从子问题入手，逐步解决大问题，每次子问题得到最优解后，会保留解的状态 也就是子问题的最优解，累计逐步逼近大问题的最优解。那总结出来就是动态规划会记住子问题已经求过的解，已求过的解来完成大问题的解，而记住求解的方式有两种方式：

1. 递归式的自底向上
2. 循环方式的自顶向下备忘录

完成小问题到大问题的汇聚。

在算法图解中对动态规划的总结有：

1. 需要在给定约束条件下优化某种指标时，动态规划 很有用。
2. 问题可分解为离散子问题时，可使用动态规划来解决。
3. 每种动态规划解决方案都涉及网格。
4. 单元格中的值通常就是你要优化的值。
5. 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
6. 没有放之四海皆准的计算动态规划解决方案的公式。

那我们来讲一道 可使用动态规划解决的题：计算组合中乘积最大的一组

给定一个长度为n的整型数组，只允许用乘法，不能用除法，请计算任意n-1个数的组合中乘积最大的一组。
点评：可以把所有可能的n-1个数的组合找出来，然后分别计算它们的乘积并比较大小。由于总共有n个数的组合，所以总的时间复杂度为O(n^2)。这时候可以使用动态规划来解决。

我来说说我的解题思路全过程：

刚开始看到这题第一想到的就是蛮力破解，就像点评中说的，但这就不是动态规划啦，想想要从小问题着手解决，哦，可以比较n个数哪个最小，比较后剔除最下的 剩余乘积不就最大啦，可我忘记了 整数可能是0和负数，这样你要枚举出来的可能乘积就多了。

那该怎么办呢，这时候就在想n-1个数组最大乘积 和 n-2个数组最大乘积应该有关联，这下有思路了：
n-1个数组最大乘积 可分解为 包含第n个数和不包含第n个数的比较：
包含第n个数有两种可能：
含n-max: n-2个数组的最大乘积 * 第n个数
含n-min: n-2个数组的最小乘积 * 第n个数
为什么这里有最小乘积呢，因为考虑到有负数，如果第n个数是负数，那最小乘积就可能变成最大乘积了。
不含n: n1 * n2 * n3 ... 第n-1个数乘积

好了，得到三个数：含n-max, 含n-min , 不含n 比较谁最大，谁就是n-1的最大乘积，那n-1数组最大乘积 需要n-2的最大乘积，那递归到最后就是比较n1, n2,n3 最大乘积，那就好比较了。
例如 数组：{-3，2，-7，12，-4，-9}

这里提出我写的代码
采用的是循环式自顶向下备忘录：

package main.java;

/**
 * Created by martin on 2018/8/9.
 */
public class DynamicProgramming01 {

    public static void main(String[] args) {

        int[] a = {-3,2,-7,12,-4};
        int size = a.length;
        int max = a[0]; // 最大乘积
        int min = a[1]; // 最小乘积

        int orderMulti = a[0]; // 这代表 不含第n数组元素的乘积

        for (int i = 2; i < size; i++) {

            orderMulti *= a[i - 1];
            max *= a[i];
            min *= a[i];

            if (min > max) {
                // 交换min和max
                int p = min;
                min = max;
                max = p;

                // 或者使用异或运算来交换min和max
                // min = min ^ max;
                // max = min ^ max;
                // min = min ^ max;
            }

            if (orderMulti > max) {
                max = orderMulti;
            }

            if (min > orderMulti) {
                min = orderMulti;
            }
        }

        System.out.println(max);
    }
}