前言
一、问题描述
二、DP步骤
1、最优子结构
- 给定序列𝑆=[$𝑠_1,𝑠_2,⋯,𝑠_𝑛$]，如果子序列[𝑆($𝑖_1$ ),𝑆($𝑖_2$ ), ⋯,𝑆($𝑖_𝑘$)]是其最大上升子序列，则[𝑆($𝑖_1$ ),𝑆($𝑖_2$ ), ⋯,𝑆(𝑖(𝑘−1) )]是子问题𝑆=[𝑠1,𝑠2,⋯,𝑆(𝑖(𝑘−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≤i<m, $S_m$<$S_i$}，可以吗？
sure
3、计算最优值
- 𝐿𝑒𝑛(𝑚)的计算同样按照自底向上的顺序进行：所有子问题的总数为n个(即，分别以每个元素为限界)；m越小，其子问题𝐿𝑒𝑛(𝑚)求解的复杂度就越低
- 当所有的𝐿𝑒𝑛(𝑚)(1≤𝑚≤𝑛)都计算完毕后，统计其中最大值，即可得到输入序列 S 的最大上升子序列
- 注意：
最大上升子序列的长度不一定等于𝑳𝒆𝒏(𝒏)
答案详解：
Len(1) = 1Len(3) = 2：找到3之前小于3的数字中，最大的Len(.)值加1，即：len(1)+1=1。Len(4)=3：找到4之前小于4的数字：1和3，最大Len(.)值加1，即：len(3)+1=3。Len(2)=2：找到2之前小于2的数字：1，最大Len(.)值加1，即：Len(1)+1=2。Len(7)=4：找到7之前小于7的数字：1，3，4，2，最大Len(.)值加1，即：Len(4)+1=4。Len(6)=4：找到6之前小于6的数字：1，3，4，2，最大Len(.)值加1，即：Len(4)+1=4。Len(8)=5：找到8之前小于8的数字：1，2，3，2，7，6，最大Len(.)值加1，即：Len(7)+1=5 或者 Len(6)+1=5
4、算法实现
时间复杂度：$n^2$
/**
* 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;
}
}
代码解说：
- 第一个for遍历：有几个元素就遍历几个，计算每个的Len(.)值。
- 第二个for遍历：遍历当前元素的最大Len(.)值。
seqSrc[i] < seqSrc[m]：过滤小于当前元素的值，Len[i] + 1 > Len[m]：找到最大值
三、优化：非DP /二分法
时间复杂度 nlog$_2$n。
1、新问题
上图中的公式中的 i ，为数组的下标
例：
- k = 4 的值有两个，Len(5) = 4，Len(6) = 4
- S[5] = 7, S[6] = 6
- 所以 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;
}
}
