Longest Increasing Subsequence

Longest Increasing Subsequence (leetcodelintcode)

Description
Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.

Clarification
What's the definition of longest increasing subsequence?
- The longest increasing subsequence problem is to find a subsequence of a given sequence 
in which the subsequence's elements are in sorted order, lowest to highest, 
and in which the subsequence is as long as possible. 
This subsequence is not necessarily contiguous, or unique.
https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4

Challenge 
Time complexity O(n^2) or O(nlogn)

解题思路

最长递增子序列的定义（维基百科）：

在计算机科学中，最长递增子序列（ longest increasing subsequence, LIS ）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。

一、动态规划

  1. 定义状态：定义一维状态变量 f[i] ，表示以第 i 个数字为结尾的 LIS 的长度。
  2. 定义状态转移函数：考虑到 LIS 是非连续的 ，对当前状态 f[i] ，上一个状态可能为 f[j], j < i ，而且此时需要满足 nums[i-1] > nums[j-1] ，在所有满足此条件的状态中取最大值 f[i] = MAX{f[j] + 1, j < i, nums[j-1] < nums[i-1]} ；如果所有 nums[i-1] < = nums[j-1], j = 1...i-1 ，那么 f[i] = 1 。
  3. 定义起点： f[0] 为前 0 个数字中 LIS 的长度，为 0 。考虑到对于每一个 i ， f[i] 至少为 1 ，所以初始化 f[i] = 1, i = 1,2...,n-1 。
  4. 定义终点：最终结果为 f[i], i = 1,2...,n-1 的最大值。
算法复杂度
  • 时间复杂度：双重循环，为 O(n^2) 。
  • 空间复杂度： O(n) 。
易错点
  1. 状态 f[i] 的索引和数组的索引 nums[i - 1] 有差值，需要注意。
  2. 需要根据实际意义初始化，可以假设一个极端的情况，一个逆序的排序数组，那么其每个状态都是 1 。

Java 实现

public
class
Solution
{

/**
     * 
@param
 nums: The integer array
     * 
@return
: The length of LIS (longest increasing subsequence)
     */
public
int
longestIncreasingSubsequence
(
int
[] nums)
{

if
 (nums == 
null
 || nums.length == 
0
) {

return
0
;
        }


int
 len = nums.length;

// status
int
[] f = 
new
int
[len + 
1
];


// initialize
// default : f[1...len] = 1
for
 (
int
 i = 
1
; i 
<
= len; i++) {
            f[i] = 
1
;

for
 (
int
 j = 
1
; j 
<
 i; j++) {

if
 (nums[i - 
1
] 
>
 nums[j - 
1
]) {
                    f[i] = Math.max(f[i], f[j] + 
1
);
                }
            }
        }


// result
int
 max = 
0
;

for
 (
int
 i = 
1
; i 
<
= len; i++) {

if
 (f[i] 
>
 max) {
                max = f[i];
            }
        }

return
 max;
    }
}

二、二分法

实现思路是，建立一个数组minLast，依次把数组nums中的元素nums[i]放入，放入的规则是：在minLast中找到第一个比nums[i]大的元素，然后替换之，这样构造的数组是一个排序数组，所以可以用二分查找。最终minLast数组长度就是 LIS 长度，需要注意的是minLast中的数并不是nums的一个 LIS ，只是长度相等。

具体到实现可能会出现这么两种情况：

  • 1） nums[i] 比 minLast 首元素小，直接替换首元素；
  • 2） nums[i] 比 minLast 所有元素都大，会放在数组尾部，数组的长度增加一；
  • 2） nums[i] 比 minLast 首元素小，比尾元素大，找到第一个比 nums[i] 的元素然后替换之。

为什么要这么做？以下是推理过程，主要参考了最长递增子序列(LIS)解法详述，理解起来稍微有点绕。

           0 1 2 3 4 5 6 7 
nums[i]:   2 5 6 2 3 4 7 4
f[i-1]:  0 1 2 3 1 2 3 4 3

我们来分析一下方法一动态规划的计算过程，在求解f[i]时，将其与每一个f[j], j < i && f[j] < f[i]，这导致每个f[i]的求解复杂度是O(n)，这里是可以改进的。

通过观察可得，在求解f[7]时，无需和nums[3], nums[4]比较，只需与nums[5]比较即可，也就是说我们考察第i个元素nums[i-1]时，如果前i - 1个元素中的任一个递增子序列，其最后一个元素比nums[i-1]小，那么就可以把nums[i-1]放在子序列后面，构成一个更长的递增子序列，不需要再和子序列前面的元素比较。

此为启发一，考察第i个元素nums[i-1]时，我们只关心前i - 1个元素中递增子序列的最后一个元素值。

在求解f[7]时，前6个元素中有两个长度为3的递增子序列2, 5, 6和2, 3, 4，而nums[6] > 6且nums[6] > 4，所以可将nums[6]放在任一序列后，构成长度为4的递增子序列。其实，只要nums[6] > 4即可接在子序列后面，无需和6比较。

此外启发二，考察第i个元素nums[i-1]时，对于同样长度的递增子序列，我们只关心尾元素中的最小值。

算法复杂度
  • 时间复杂度： n 次二分查找，为 O(nlogn) 。
  • 空间复杂度： O(n) 。

Java 实现

public
class
Solution
{

/**
     * 
@param
 nums: The integer array
     * 
@return
: The length of LIS (longest increasing subsequence)
     */
public
int
longestIncreasingSubsequence
(
int
[] nums)
{

if
 (nums == 
null
 || nums.length == 
0
) {

return
0
;
        }


int
 len = nums.length;

int
[] minLast = 
new
int
[len + 
1
];
        minLast[
0
] = -
1
;

for
 (
int
 i = 
1
; i 
<
= len; i++) {
            minLast[i] = Integer.MAX_VALUE;
        }


for
 (
int
 i = 
0
; i 
<
 len; i++) {

// find the first number in minLast 
>
 nums[i]
int
 index = binarySearch(minLast, nums[i]);
            minLast[index] = nums[i];
        }


for
 (
int
 i = len; i 
>
= 
1
; i--) {

if
 (minLast[i] != Integer.MAX_VALUE) {

return
 i;
            }
        }

return
0
;
    }


// find the first number 
>
 num
private
int
binarySearch
(
int
[] minLast, 
int
 num)
{

int
 start = 
0
, end = minLast.length - 
1
;

while
 (start + 
1
<
 end) {

int
 mid = start + (end - start) / 
2
;

if
 (minLast[mid] 
<
 num) {
                start = mid;
            } 
else
 {
                end = mid;
            }
        }

        Edit Distance

Edit Distance ( leetcode lintcode )
Description
Given two words word1 and word2, 
find the minimum number of steps required to convert word1 to word2. 
(each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character

Example
Given word1 = "mart" and word2 = "karma", return 3.
解题思路

动态规划，本题与 LCS 类似。
定义状态：定义 f[i][j] 为字符串 A 的前 i 个字符 匹配 字符串 B 的前 j 个字符需要执行的最少操作数量 。
定义状态转移函数：对于当前状态 f[i][j] ，由于涉及操作较多，所以需要详细讨论：
A[i - 1] == B[j - 1] 时。
无操作：上一个状态可能是 f[i - 1][j - 1] ，此时无需任何操作。
插入操作：如果需要对 A 末尾执行一次插入操作，插入之后 A[i] == B[j - 1] ，那么执行操作前 A 的前 i 个字符和 B 的前 j - 1 个字符相匹配，上一个状态是 f[i][j - 1] 。
删除操作：如果需要对 A 末尾执行一次删除操作，删除之后 A[i - 2] == B[j - 1] ，那么执行操作前 A 的前 i - 1 个字符和 B 的前 j 个字符相匹配，上一个状态是 f[i - 1][j] 。
综上， 当前状态需要取以上三种情况的最小值。
A[i - 1] != B[j - 1] 时。
替换操作：将 A 的第 i 个字符替换为 B 的前 j 个字符，那么执行操作前 A 的前 i - 1 个字符和 B 的前 j - 1 个字符相匹配，上一个状态是 f[i - 1][j - 1] 。
插入操作：如果需要对 A 末尾执行一次插入操作，插入之后 A[i] == B[j - 1] ，那么执行操作前 A 的前 i 个字符和 B 的前 j - 1 个字符相匹配，上一个状态是 f[i][j - 1] 。
删除操作：如果需要对 A 末尾执行一次删除操作，删除之后 A[i - 2] == B[j - 1] ，那么执行操作前 A 的前 i - 1 个字符和 B 的前 j 个字符相匹配，上一个状态是 f[i - 1][j] 。
综上，当前状态需要取以上三种情况的最小值。
定义起点：起点 f[0][0] == 0 ，当 A 为空或 B 为空时，对应的状态函数 f[0][j] 或f[i][0] ，从起点出发分别需要 j 或 i 次操作。
定义终点：最终结果即为 f[n][m] 。
易错点：

在处理边界情况时，如果其中一个字符串长度为 0，程序时可以处理的，所以只要考虑字符串为空的情况即可。
Java 实现
public class Solution {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    public int minDistance(String word1, String word2) {
        // write your code here
        if (word1 == null || word2 == null) {
            return 0;
        }

        int n = word1.length();
        int m = word2.length();        

        // state
        int[][] f = new int[n + 1][m + 1];

        // initialize
        for (int i = 0; i <= n; i++) {
            f[i][0] = i;
        }
        for (int j = 1; j <= m; j++) {
            f[0][j] = j;
        }

        // top down
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = Math.min(f[i - 1][j - 1], 
                                       Math.min(f[i][j - 1] + 1, f[i - 1][j] + 1));
                } else {
                    f[i][j] = Math.min(f[i - 1][j - 1], 
                                       Math.min(f[i - 1][j], f[i][j - 1]))
                                        + 1;
                } 
            }
        }

        // end
        return f[n][m];
    }
}
优化空间（滚动数组）：
观察状态转移函数，f[i][j] 由 f[i - 1][j] 或 f[i][j - 1] 决定，与前 i - 2 行无关，所以可利用滚动数组进行优化。
public class Solution {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    public int minDistance(String w1, String w2) {
        if (w1 == null || w2 == null ) {
            return 0;        
        }

        int m = w1.length();
        int n = w2.length();
        // status
        int[][] f = new int[2][n + 1];
        // initialize
        for (int i = 0; i <= n; i++) {
            f[0][i] = i;
        }

        for (int i = 1; i <= m; i++) {
            f[i % 2][0] = i;
            for (int j = 1; j <= n; j++) {
                if (w1.charAt(i - 1) == w2.charAt(j - 1)) {
                    f[i % 2][j] = Math.min(f[(i - 1) % 2][j - 1], Math.min(f[(i - 1) % 2][j], f[i % 2][j - 1]) + 1);
                } else {
                    f[i % 2][j] = Math.min(f[(i - 1) % 2][j - 1], Math.min(f[(i - 1) % 2][j], f[i % 2][j - 1])) + 1;
                }
            }
        }

        return f[m % 2][n];
    }
}
参考

Edit Distance | 九章算法
if
 (minLast[start] 
>
 num) {

return
 start;
        }

return
 end;
    }
}

参考

  1. Longest Increasing Subsequence | 九章算法
  2. [LeetCode] Longest Increasing Subsequence 最长递增子序列 | Grandyang
  3. 最长递增子序列(LIS)解法详述 | 杰 & C++ & Python & DM

results matching ""

    No results matching ""