动态规划解决最大乘积系列问题（碾压暴力枚举）java

目录

1.例题

题目描述

输入n个元素组成的子串S，你需要找出一个乘积最大的连续的子串。

如果这个最大的乘积不是正数，应输出0(表示无解)。

输入

第一行是一个整数n(1<=n<=18)。

第二行是n个整数。其中每个整数的范围是[-10,10]。

**输出 **

输出一行包含一个整数，输出最大乘积。

**测试数据 **

见代码。

2. 思路分析

基本思想

题目类似背包问题，，其基本思想可以使用动态规划：记住已经解决过的子问题的解。求解，即在遍历数据的时候，将遍历过程中求得的最大乘积记录下来，再继续遍历，通过每次遍历，动态的更新最大乘积，最终求得的就是最终解。

对于此类题目可以定义两个变量max和min，用来记录过程中的最大值和最小值。cur表示计算过程中的当前要计算的数据。每次计算过程中，max取Max.(cur，curmax，curmin)中的最大值，min取Min.(cur，curmax，curmin)中的最小值。

具体步骤

1） 初始化cur，max，min数据，默认都为第一个数。

2）循环计算数组元素。

3）每次循环max，min都乘以当前元素cur。并用临时变量保存。

4）计算新的max和min并重新赋值。

5）计算过程中新的最大值ans=Max(max，ans)。

6）遍历完后打印ans。

3.代码实现

import java.util.Scanner;

public class Main {
    static long[] nums;// 用来存放数据

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        /**
         * long cur 当前数据 long max 最大数 long min 最小数 long ans 最终结果
         */
        long cur, max, min, ans = 0;
        // 录入数据
        for (int i = 0; i < m; i++)
            nums[i] = scanner.nextLong();
        // 初始化数据，默认都为第一个数
        cur = nums[0];
        max = nums[0];
        min = nums[0];
        for (int i = 1; i < m; i++) {
            cur = nums[i];// 当前处理的数
            long tempmax = max * cur;// 当前数cur乘以最大数max，定义一个临时变量tempmax储存
            long tempmin = min * cur;// 当前数cur乘以最小数min，定义一个临时变量tempmin储存
            // 新的max在上面三个数中产生
            /* 因为max在下一步求min时还要用到，因此这里定义一个临时变量储存newmax */
            long newmax = Math.max(cur, Math.max(tempmax, tempmin));
            min = Math.min(cur, Math.min(tempmax, tempmin));
            max = newmax;// max使用完后，将新的newmax赋值给max
            ans = Math.max(ans, max);// 数据处理过程中的答案在ans和max中产生
        }
        System.out.println(ans);
    }

}

4.DP小结

注意

动态规划（ Dynamic Programming ）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）
动态规划可以通过填表的方式来逐步推进，得到最优解．