本文共 701 字，大约阅读时间需要 2 分钟。
问题A：
最长上升子序列：维护一个长度数组，时间O(N*logN)
若要返回子序列，则再维护一个位置数组。其中，长度数组含义为，L[i] 表示长度必须为i时，结尾的最小位置，其中最大长度即为所有最长子序列的长度。
位置数组与原数组等长，loc[i]表示原数组字符构成子序列后的对应位置。例如：2，1，5，3，6，4，8，9，7
最后长度数组为，1，3，4，7，9，最大长度为5，更新为logN 位置数组为，1，1，2，2，3，3，4，5，4，依据从5开始往回找4，3，…，1，得到字符串，9，8，4，3，1。问题B：
信封嵌套问题：结构体二级排序+最长上升子序列，时间O(N*logN)
对x增序排序，在对y求最长上升，即为答案。
问题C：
最长公共子序列：重复字符较少：用哈希+最长上升，维护哈希表{字符，<多个对应位置>}，最坏O(NMlogN) ，重复字符较少，O(max{N,M})
重复字符较多：dp，时间O(N*M)dp方法维护一个二维表，dp[i][j] 表示 strA[0…i] 和 strB[0…j]的最大公共子序列。
dp[i][j] 依赖 dp[i-1][j-1]和dp[i][j-1]，即左上角元素和左邻元素。 所以，空间压缩可以循环i次，维护dp[j]长度的表。问题D：
最长公共子串：如上问题，采用dp，dp[i][j]表示strA[0…i]和strB[0…j]的最长公共子串。
时间O(N*M) 空间可以进一步降至O(1)观察dp表特点，dp[i][j] 只依赖dp[i-1][j-1]，故采用斜线计算，从左上往右下方向计算，只需要保存一个临时值即可。
转载地址：http://abwji.baihongyu.com/