1.例题
题目描述
- 思路分析
基本思想
具体步骤
3.代码实现
4.DP小结
注意
1.例题
题目描述
输入n个元素组成的子串S，你需要找出一个乘积最大的连续的子串。
如果这个最大的乘积不是正数，应输出0(表示无解)。
输入
第一行是一个整数n(1<=n<=18)。
第二行是n个整数。其中每个整数的范围是[-10,10]。
输出
输出一行包含一个整数，输出最大乘积。
测试数据
见代码。
- 思路分析
基本思想
题目类似背包问题，，其基本思想可以使用动态规划：记住已经解决过的子问题的解。求解，即在遍历数据的时候，将遍历过程中求得的最大乘积记录下来，再继续遍历，通过每次遍历，动态的更新最大乘积，最终求得的就是最终解。
对于此类题目可以定义两个变量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 ）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）
动态规划可以通过填表的方式来逐步推进，得到最优解．
