BAT最热笔试题：最长递增子序列的六种解法(gitbuh项目：AlgorithmPractice)ljfirst的博客-

项目介绍

• 本项目通过分解各大厂的常见笔面试题，追本溯源至数据结构和算法的底层实现原理，知其然知其所以然；
• 建立知识结构体系，方便查找，欢迎更多志同道合的朋友加入项目AlgorithmPractice，（欢迎提issue和pull request）。

什么是最长递增子序列

• 在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。
• 学完这道题的六种解法，就可以去秀面试官了。

六种解法

• 1、暴力法
• 2、动态规划法
• 3、分治法
• 4、字符串对比法
• 5、分支限界法
• 6、扑克法

正文开始

1、暴力法

• 代码实现：LIS_Violence，测试用例：TestLIS_Violence
• 设计思路：
  • 遍历字符串的所有组成可能，对这些可能进行判断是否符合递增规律，并统计最长的子串长度。
• 主要代码：

//外循环是字符串的起始位置 for (int beginLocation = 0; beginLocation < sequence.length() - 1; beginLocation++) { //内部循环是暴力字符串的长度增长空间 for (int subLength = 1; subLength < sequence.length() - beginLocation; subLength++) {          sb = new StringBuffer();          sb.append(sequence.charAt(beginLocation)); dealString(sb, sequence, beginLocation, subLength); } } 

//生成字符串，其中beginLocation的字符是必须包含的 public void dealString(StringBuffer sb, String s, int beginPosition, int strdepth) { if (strdepth == 0 && judge(sb.toString())) { if (sb.length() > best_length) {                 best_length = sb.length(); } return; } for (int i = beginPosition + 1; i < s.length(); i++) {           sb.append(s.charAt(i)); dealString(sb, s, i, strdepth - 1);           sb.deleteCharAt(sb.length() - 1); } } 

• 注意事项：
  • 每次用于统计的temp数组或者temp List，在进行下一次运算的时候需要清空。
  • 遍历字符串的所有组成是采用递归做的，递归前后的取舍需要注意，特别是StringBuffer.deleteCharAt()方法，这里面的参数不能用当前的循环值，而应该是StringBuffer.length() – 1。

2、动态规划法

• 代码实现：LIS_Dynamic，测试用例：TestLIS_Dynamic
• 设计思路：
  • 对于字符串中任意某点 J 的最大子串，等于其前面的最大子串数加一。
  • 状态转换方程：longest[i] = (longest[j] + 1) > longest[i] ? (longest[j] + 1) : longest[i];
• 主要代码：

for (int i = 0; i < length; i++) { for (int j = 0; j < i; j++) { if ((intArray[j] < intArray[i])) {              longest[i] = (longest[j] + 1) > longest[i] ? (longest[j] + 1) : longest[i]; } } if (longest[i] > best) {          best = longest[i];          point = i; } } 

• 注意事项：

3、分治法【局限于连续子串，本题仅供参考】

• 代码实现：LIS_Divide，测试用例：TestLIS_Divide
• 设计思路：
  • 对于指定字符串，一定存在某个最大长度的递增子序列，现在把指定字符串分成左边和右边，那么这个最大的递增子序列，要么存在于左边子串，要么存在于右边子串，要么横跨左右（这特么不是废话）。
  • 对于横跨两边的子串，分别向左扩展找出小于其的最长递增子序列，向右同理，但是本题我在做得时候，我仅仅做了大小判断，所以这种方法只能解决连续的递增问题，非连续子串的递增，可能需要才有动态规划的方式。
• 主要代码：

public int divide(int[] stringArr, int left, int right) { if (left < right) { int mid = (left + right) / 2; int leftValue = divide(stringArr, left, mid); int rightValue = divide(stringArr, mid + 1, right); int midValue = middleHandle(stringArr, left, right); return Math.max(Math.max(leftValue, rightValue), midValue); } return 0; } 

//向左扩展 while (leftPoint - 1 >= left && stringArr[leftPoint] > stringArr[leftPoint - 1]) {     count++;     leftPoint--; } //向右扩展 while (rightPoint + 1 <= right && stringArr[rightPoint] < stringArr[rightPoint + 1]) {     count++;     rightPoint++; } 

• 注意事项：
  • 本解法不要用于解决最长递增子序列，仅仅用于计算最长连续递增子串

4、字符串对比法

• 代码实现：LIS_Lcs，测试用例：TestLIS_Lcs
• 设计思路：
  • 将字符串转出数组，进行排序
  • 排序后的数组，进行去重（考虑递增不单调，不存在重复的数据）
  • 将去重后的数组再转成字符串与原字符串进行最长公共子序列对比（其本质还是动态规划的思想）。
• 主要代码：

//进行快速排序 QuickSortDuplexing q = new QuickSortDuplexing(); q.sortMethod(ints); //因为是递增序列，所以要去重 HashMap hashMap = new HashMap(); for (int i = 0; i < c.length; i++) {     hashMap.put(ints[i], 1); } String temp = hashMap.keySet().toString().replace(",", "").replace("[", "").replace("]", "").replace(" ", ""); //再进行最长子序列比较 LCS lcs = new LCS(); int length = lcs.count(temp, sequence).getCommondLength(); 

• 注意事项：
  • 去重选取的是hashmap的key
  • hashmap转String，需要replace很多，暂时没找到比较好的办法。

5、分支限界法

• 代码实现：LIS_Branch，测试用例：TestLIS_Branch
• 设计思路：
  • 分支限界法是对暴力法的改进，对一些显而易见的条件进行删除。
  • 比如：
    • 当前temp的值加上剩下待遍历的距离，小于等于最优值的时候，就没有必要再继续下去了。
    • 剩下的待遍历距离小于当前的最优解，就没有必要再继续下去了。
• 主要代码：

//剩下的待遍历距离小于当前的最优解，就没有必要再继续下去了。 for (int i = 1; count_best <= length - i; i++) {     list_temp = new ArrayList();     list_temp.add(StringArray[i - 1]);     count_temp = 1; count(i); } 

//当前temp的值加上剩下待遍历的距离，小于等于最优值的时候，就没有必要再继续下去了。 if ((length - 1) - depth + (count_temp + 1) <= count_best) { return; } if (count_temp > count_best || depth == length - 1) { //更新最优解，并继续下去 if (count_temp > count_best) {         list_best = new ArrayList<>(list_temp);         count_best = count_temp; } //达到终点，停止递归 if (depth == length - 1) { return; } } //分支递归 for (int i = depth; i < length; i++) { if (list_temp.get(count_temp - 1) < StringArray[i]) {         count_temp++;         list_temp.add(StringArray[i]); count(i + 1);         list_temp.remove(list_temp.get(--count_temp)); } } 

• 注意事项：
  • List赋值的时候，这样才不会造成引用跟随：list_best = new ArrayList<>(list_temp);

6、扑克法【扑克法本质是分治思想】

• 代码实现：LIS_Poker，TestLIS_Poker
• 设计思路：
  • 按照扑克牌的玩法，第一张自启一摞
  • 第二张比第一张小，则压在第一张上
  • 第二张比第一张大，则另启一摞。
  • 第三张比第二张小，则压在第二张上
  • 第三张比第二张大，则另启一摞。
  • 最后分成的摞数，就是我们要求的最长递增子序列数，你一定可以找到一个组合，位于不同的摞中，是严格递增的存在，数学证明略。
• 主要代码：

for (int i = 0; i < count; i++) {  left = 0;  right = piles;  poker = intArray[i]; while (left < right) {   mid = (left + right) / 2; if (poker < top[mid]) {    right = mid;// ? right = mid-1; } else if (poker > top[mid]) {    left = mid + 1; } else {    right = mid; } } if(left == piles){   piles++; }  top[left] = poker; } 

• 注意事项：
  • 限于表达能力，扑克法描述可能表述的不清晰，大家可以参考这篇详细的博文：动态规划设计之最长递增子序列。