动态规划解决最长上升子序列LIS避坑

vlambda
2020-04-14

动态规划解决最长上升子序列LIS避坑

LIS最长上升子序列

虽然这个问题归类于动态规划，而且也已经被网上炒来炒去，但是当我第一次看到这个需求，分析来分析去还是没有很好的思路，特意研究了好一阵子，决定还是记录下来，把思路和总结刻下来，不能再同一个地方摔了又摔！

动态规划就是每一步都选择最优的，最后结果肯定也是最优的

首先需求是这样的：

求数组的最大上升子序列长度，如{1,3,2,4,5}最大上升子序列为1，2，4，5或1，3，4，5。长度为4。

给定的一个无序数组，找出其中不断上升的数组序列。由于一个无序数组的最大上升子序列可能会有很多个，如果要把这个序列（们）找出来，问题会更加困难一点，暂且只说找出最大长度，这样答案就唯一了。

- 直男癌思路——穷举 -

这个想法是最容易想到的，就是用脚趾头想出的思路。

把所有情况都罗列出来，必定会找到最终答案，这种情况如果数组很大的话，可能就需要银河计算机了。这个方法可不可取视数组情况来定吧。

————

- 进阶——找到当前最长的，之前的就放弃 -

从前往后找每个下标位置的元素是取还是舍。

这是没问题的，但是会发现这是一个一对多的检索方式，如果分支足够多的，这个方法可以让你入手一台外星人配置的电脑。

- 换一个方向从后往前找 -

既然从前往后找，会出现很多分支，会浪费很多资源，那么就从后往前找。

找以当前元素为最后一个元素时的子序列长度。这样情况就会简单多了，每次遍历都把该长度记录下来，最后遍历一下这个记录长度的数组，找出最大值就可以了。

- 代码实现 -

package com.mine;
import java.util.Arrays;
public class Lis{ public static void main( String[] args ){ int[] arr = {1,3,2,4,5}; int len = lengthOfArray(arr); System.out.println("result:"+len); }
 // 对数组长度为0和1的特殊情况进行处理 private static int lengthOfArray(int[] arr) { Integer x = checkLength(arr); if (x != null) return x;
 /* 定义存储当前长度的数组 其实我之前想把这里定义为集合
            这样后边找最大值可以调用max函数
 但是我的jdk是1.8的，List.of是用不了，
 鱼和熊掌不可兼得了*/ int[] dps = new int[arr.length]; Arrays.fill(dps, 1); // 将所有位置初始化为1
 // 遍历原数组对dps赋值 setValueOfDpi(arr, dps);

 // 遍历dps，查找最大值下标
 int max = 1; for (int i = 0; i < dps.length; i++) { if (dps[i] > max){ max = dps[i]; } } return max; }
 // 这里应该算是核心代码 private static void setValueOfDpi(int[] arr, int[] dps) { for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { // 这两个条件理解了 // 整个问题就好解决了 if (arr[j] < arr[i] && dps[j] + 1 > dps[i]){ dps[i] = dps[j] + 1; } } } }
 /* * 对数组的长度判断0和1的情况 * @param arr * @return */ private static Integer checkLength(int[] arr) {
 if (arr.length == 0){ return 0; } if (arr.length == 1){ return 1; } return null; }}