文章目录

• 前言
• 一、问题描述
• 二、DP步骤
• • 1、最优子结构
  • • a、限界上升子序列
    • b、最优子结构性质
  • 2、状态表示和递推方程
  • 3、计算最优值
  • 4、算法实现
• 三、优化：非DP /二分法
• • 1、新问题
  • 2、算法实现

前言

一、问题描述

二、DP步骤

1、最优子结构

• 给定序列𝑆=[𝑠₁,𝑠₂,⋯,𝑠_𝑛]，如果子序列[𝑆(𝑖₁ ),𝑆(𝑖₂ ), ⋯,𝑆(𝑖_𝑘 )]是其最大上升子序列，则[𝑆(𝑖₁ ),𝑆(𝑖₂ ), ⋯,𝑆(𝑖_(𝑘−1) )]是子问题𝑆=[𝑠₁,𝑠₂,⋯,𝑆(𝑖_(𝑘−1) )]的最大上升子序列吗？
• 例：给定 S = [1, 3, 4, 2, 7, 9, 6, 8]，最大上升子序列可为 [1, 3, 4, 6, 8]，最大长度为5。
• [1, 3, 4, 6]显然不是[1, 3, 4, 2, 7, 9, 6]的最大上升子序列，因为[1, 3, 4, 7, 9]是其最大上升子序列。
  注意：可以同时有多个最大上升子序列！每个的最大值都不相同
• 如果直接把最大上升子序列的长度作为规划目标，那么该问题不具备最优子结构性质（因为可能同时有多个最大上升子序列，使得最优子结构不成立）。只能采用间接的办法，引入一些中间目标作为动态规划的对象。

a、限界上升子序列

b、最优子结构性质

2、状态表示和递推方程

公式讲解：只求长度，不求具体的子序列

• 逐一找出1—（m-1）个元素中所有小于S_m的元素S_i及其对应的Len(S_i)值，然后从中取最大的一个Len(.)值，然后加1。【 1–i个元素中所有大于Sm的元素的Len(.)值全都不予考虑】

• 如果精简为max{Len(i)+1 | 1≤im>S_i}，可以吗？
  sure

3、计算最优值

• 𝐿𝑒𝑛(𝑚)的计算同样按照自底向上的顺序进行：所有子问题的总数为n个(即，分别以每个元素为限界)；m越小，其子问题𝐿𝑒𝑛(𝑚)求解的复杂度就越低
• 当所有的𝐿𝑒𝑛(𝑚)(1≤𝑚≤𝑛)都计算完毕后，统计其中最大值，即可得到输入序列 S 的最大上升子序列
• 注意：最大上升子序列的长度不一定等于𝑳𝒆𝒏(𝒏)
  
  答案详解：

1. Len(1) = 1
2. Len(3) = 2：找到3之前小于3的数字中，最大的Len(.)值加1，即：len(1)+1=1。
3. Len(4)=3：找到4之前小于4的数字：1和3，最大Len(.)值加1，即：len(3)+1=3。
4. Len(2)=2：找到2之前小于2的数字：1，最大Len(.)值加1，即：Len(1)+1=2。
5. Len(7)=4：找到7之前小于7的数字：1，3，4，2，最大Len(.)值加1，即：Len(4)+1=4。
6. Len(6)=4：找到6之前小于6的数字：1，3，4，2，最大Len(.)值加1，即：Len(4)+1=4。
7. Len(8)=5：找到8之前小于8的数字：1，2，3，2，7，6，最大Len(.)值加1，即：Len(7)+1=5 或者 Len(6)+1=5

4、算法实现

时间复杂度：n²

/*** DP算法之最大上升子序列问题*/
public class Main4 {public static int MAXN = 100;public static void main(String[] args) {int[] seqSrc = {1, 3, 4, 2, 7, 6, 8};int i = LISLength(7, seqSrc);System.out.println(i);}public static int LISLength(int num, int[] seqSrc) {int[] Len = new int[MAXN];int res = 1;//设第m个数的值为上界for (int m = 0; m < num; m++) {  //每个新m为上界时，Len[m]总是从1开始Len[m] = 1;     for (int i = 0; i < m; i++)//遍历所有以第i个数为上界的长度，从中选出符合max公式条件的最大值加1，就是Len[m]。if (seqSrc[i] < seqSrc[m] && Len[i] + 1 > Len[m])   Len[m] = Len[i] + 1;//记录从len[1]到len[m]中的最大值，res为最大公共子序列长度，最后的解res = (res > Len[m] ? res : Len[m]);  }return res;}
}

代码解说：

1. 第一个for遍历：有几个元素就遍历几个，计算每个的Len(.)值。
2. 第二个for遍历：遍历当前元素的最大Len(.)值。
   • seqSrc[i] < seqSrc[m] ：过滤小于当前元素的值，
   • Len[i] + 1 > Len[m]：找到最大值

三、优化：非DP /二分法

时间复杂度 nlog₂n。

1、新问题

上图中的公式中的 i ，为数组的下标
例：

1. k = 4 的值有两个，Len(5) = 4，Len(6) = 4
2. S[5] = 7, S[6] = 6
3. 所以 T[k=4] = 6。
   
   
   

2、算法实现

/*** DP之最大上升子序列：时间复杂度  nlog2n*/
public class Main5 {public static void main(String[] args) {int[] seqSrc = {1, 3, 4, 2, 7, 6, 8};int i = lengthOfLIS(seqSrc);System.out.println(i);}public static int lengthOfLIS(int[] arr) {if (arr == null || arr.length == 0) {return 0;}int[] ends = new int[arr.length];ends[0] = arr[0];int right = 0;int l = 0;int r = 0;int m = 0;int max = 1;for (int i = 1; i < arr.length; i++) {l = 0;r = right;while (l <= r) {m = (l + r) / 2;if (arr[i] > ends[m]) {l = m + 1;} else {r = m - 1;}}right = Math.max(right, l);ends[l] = arr[i];max = Math.max(max, l + 1);}return max;}
}