Longest increasing/common subsequence/substring

这是一类常见的dp问题。 从题目就可以看出来，主要分两类，一类是substring，一类是subsequence， 前者必须连续。 We will discuss the following three questions here: 1) Longest increasing subsequence 2) Longest common subsequence 3) Longest common substring

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity?

L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1 To get LIS of a given array, we need to return max(L(i)) where 0 < i < n L(i) 表示的就是到num[i]为止的最长递增序列的长度，更新就是往回看。。。

public int lengthOfLIS (int[] nums]){
  int n = nums.length;
  int[] dp = new int[n];
  int max = 1;
  for (int i = 1; i < n; i++){
  //look back to see if we can append nums[i] in the subsequence
    for (int j = 0; j < i; j++){
      if (nums[i] > nums[j] && dp[i] < dp[j] + 1){
        dp[i] = dp[j] + 1;
      }
    }
    //pick maximum among dp[].
    max = Math.max(max, dp[i]);
  }
  return max;
}

The time complexity is O(N^2). The optimal solution is O(NLogN). 看到logn应该会联想到binary search。最优解正是应用了这个方法。

public int getLenOfLIS(int[] nums){
  if (nums == null || nums.length == 0) return 0;
  int[] tails = new int[nums.length];
  int size = 0;
  for (int x : nums){
    int i = 0, j = size;
    while (i != j){
      int mid = (i + j) / 2;
      if (x <= tails[mid]){
        j = mid;
      }else {
        i = mid + 1;
      }
    }
    tails[i] = x;
    if (i == size) size++;
  }
  return size;
}

Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4. 这题直接暴力法的话是O(2^n),当两个字符串每个字符都不match的时候。 dp的话就是画表法。Time complexity is O(M * N)

public int LCS(String a, String b){
  int[][] dp = new int[a.length() + 1][b.length() + 1];
  for (int i = 1; i <= a.length(); i++){
    for (int j = 1; j <= b.length(); j++){
      if (a.charAt(i - 1) == b.charAt(j - 1)){
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[a.length()][b.length()];

Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

Examples :
Input : X = "GeeksforGeeks", y = "GeeksQuiz" Output : 5 The longest common substring is "Geeks" and is of length 5.
Input : X = "abcdxyz", y = "xyzabcd" Output : 4 The longest common substring is "abcd" and is of length 4.
Input : X = "zxabcdezy", y = "yzabcdezx" Output : 6 The longest common substring is "abcdez" and is of length 6.
暴力解法是找到所有的substring,total m^2, m is the length of the string X. then compare each s whether or not a substring in Y, if we use KMP, it could be O(n), so the total time complexity for brute force method will be O(N * M^2). The longest common suffix has following optimal substructure property
LCSuff(X, Y, m, n) =
LCSuff(X, Y, m-1, n-1) + 1 if X[m-1] = Y[n-1]
0 Otherwise (if X[m-1] != Y[n-1])

The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m, n) =
Max(LCSuff(X, Y, i, j)) where 1 <= i <= m and 1<= j <=n

public int getLCSlen(String a, String b){
  int n = a.length();
  int m = b.length();
  int[][] dp = new int[n + 1][m + 1];
  int result = 0;
  for (int i = 1; i <= n; i++){
    for (int j = 1; j <= m; j++){
      if (a.charAt(i - 1) == b.charAt(j - 1)){
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }else {
        dp[i][j] = 0;
      }
      result = Math.max(result, dp[i][j]);
    }
  }
  return result;

以上。