2017-04-28

算法设计与分析[0010] Longest Increasing Subsequence（最长递增子序列）

300. Longest Increasing Subsequence

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.

给出一个序列 $a_1, a_2, …, a_n$，求它的一个子序列（设为 $s_1, s_2, …, s_n$ ），使得这个子序列满足这样的性质：$ s_1 < s_2 < s_3 <…< s_n $ 并且这个子序列的长度最长，输出这个最长的长度。实际上，诸如最长下降子序列，最长不上升子序列等问题都可以看成同一个问题，仔细思考就会发现，这其实只是 $<$ 符号定义上的问题，并不影响问题的实质。
转化为图的最长路径问题（$O(N^2)$）
解决最长递增子序列的一种方法是将其转换为图的最长路径问题（可以说是一种归约思想）
- 为序列中的每个元素 $a_i$ 建立一个对应的节点 i。
- 对于任意两个可能在某递增序列中存在递进关系的元素 $a_i$ 和 $a_j$（即，同时满足 $ i < j $，且 $ a_i < a_j $），增加一条连接二者对应节点的有向边 $i->j$。
- 基于简单的动态规划，寻找转化后的图中的最长路径。如下图：
基于上述思路的代码实现如下：

int graph[10000][10000];
int lengthOfLIS(int* nums, int numsSize) {
    //sanity check
    if(numsSize < 1) {
        return 0;
    }
    
    for(int fromIdx=0; fromIdx<numsSize; fromIdx++) {
        for(int toIdx=fromIdx+1; toIdx<numsSize; toIdx++) {
            graph[fromIdx][toIdx] = 0;
        }
    }
    
    // convert the sequence into a directed graph
    for(int fromIdx=0; fromIdx<numsSize; fromIdx++) {
        for(int toIdx=fromIdx+1; toIdx<numsSize; toIdx++) {
            if(nums[toIdx] > nums[fromIdx]) {
                graph[fromIdx][toIdx] = 1;
            }
        }
    }
    
    // find the longest path <--> LIS
    int L[numsSize];
    for(int idx=0; idx<numsSize; idx++) {
        int localMax = 0;
        for(int fromIdx=0; fromIdx<=idx; fromIdx++) {
            if(graph[fromIdx][idx] == 1) {
                if(L[fromIdx] > localMax) {
                    localMax = L[fromIdx];
                }
            }
        }
        L[idx] = localMax + 1;
    }
    int globalMax = 0;
    for(int idx=0; idx<numsSize; idx++) {
        if(L[idx] > globalMax) {
            globalMax = L[idx];
        }
    }
    return globalMax;
}

需要特别留意的是：存储转换后的图的邻接矩阵 graph，实际上应该是一个动态大小的二维数组，然而，由于 堆栈内存限制，只能将其预设为足够大小的二维数组，作为全局或者 static 变量在堆中开辟内存，避免 Runtime Error（堆栈溢出）的错误。
在求解转换后的图中的最长路径时，采用了动态规划的方法
- $L[idx]$ ：第 idx 个元素对应的节点的最长路径（从根（序列的第一个元素）出发）；
- $L[idx+1]$ 显然为带有最大最长路径的前驱节点的最长路径+1。
算法是可行准确的，但是运行效率就不敢恭维了。

动态规划（$O(N^2)$）

既然是动态规划法，那么最重要的自然就是寻找子问题，对于这个问题，我们找到他的子问题
- 用$dp[idx]$ 来存放以 $a_{idx}$ 结尾的最大递增子序列长度。
找到子问题之后，接下来就是关于子问题如何求解的问题（状态转移方程）
- 想求以 $a_{idx}$ 结尾的最大递增子序列的长度，我们就需要遍历 $idx$ 之前的所有位置 $ i, i \in [1, idx-1]$，在这些 $ i $ 中，找出 $ a[i] < a[idx]$，计算能产生最大 $dp[i]$ 的 $i$，之后就可以求出 $dp[idx]$： $dp[idx] = max(dp[i]) + 1, i \in [1, idx-1] \&\& a_i < a_{idx}$。
对序列中的每一个元素都计算以他们各自结尾的最大递增子序列的长度，这些长度的最大值，就是我们要求的问题 —— 序列的最大递增子序列。

int lengthOfLIS(int* nums, int numsSize) {
    // sanity check
    if(numsSize <= 0) {
        return 0;
    }
    
    // dp[idx]: the length of the LIS ending with the idx-th element
    int dp[numsSize];
    // prev[idx]:record the previous index of the LIS ending with the idx-th element
    int prev[numsSize];
    
    for(int idx=0; idx<numsSize; idx++) {
        // the maximum length of previous index LIS ending with an element not greater than current element 
        int localIdxMax = 0;
        for(int i=0; i<idx; i++) {
            if(nums[i] < nums[idx] && dp[i] > localIdxMax) {
                localIdxMax = dp[i];
                prev[idx] = i;
            }
        }
        dp[idx] = localIdxMax + 1;
    }
    
    // the longest increasing subsequence should ending with one index-th element
    int totalMax = 0;
    for(int idx=0; idx<numsSize; idx++) {
        if(dp[idx] > totalMax) {
            totalMax = dp[idx];
        }
    }
    return totalMax;
}

因为避免了将问题转化为图这一繁琐的步骤，所以虽然同为 $O(N^2)$ 的复杂度，这种方法效率明显提升了。

耐心排序法（$O(N logN)$）

上面的解法时间复杂度仍然为 $O(N^2)$，仔细分析一下原因，之所以慢，是因为对于每一个新的位置 $idx$ 都需要遍历 $idx$ 之前的所有位置 $ i, i \in [1, idx-1]$，找出之前位置的最长递增子序列长度。我们是不是可以有一种方法能不用遍历之前所有的位置，而可以更快的确定 $i$ 的位置呢？
- 举个例子，比如序列 $1, 3, 5, 2, 8, 4, 6$ 这个例子中，当到 6 时，我们一共可以有四种(1)不同长度；(2)保证该升序序列在同长度升序序列中末尾最小的升序序列
  - 1
  - 1,2
  - 1,2,4
  - 1,2,4,6
- 以上这些序列都是未来有可能成为最长序列的候选序列。这样，每来一个新的数，我们便按照以下规则更新这些序列：
  - 如果 $idx$ 元素比所有序列的末尾都大，说明有一个更长的递增序列产生，我们把最长的序列复制一遍，并加上这个元素。
  - 如果 $idx$ 元素比所有序列的末尾都小，说明长度为1的序列可以更新了，更新为这个更小的末尾。
  - 如果刚好在中间，则更新那个末尾数字刚刚大于等于自己的那个序列，说明那个长度的序列可以更新了。
基于上面的例子，我们可以推导出这样的一种思路
- $A[i]$ 数组用来记录长度为 $i$ 的递增子序列的末尾元素的最小值
  - 其中$ i \leq numsSize$
  - 数组 $A[i]$ 的 size 为 $numsSize+1$
  - 我们很容易能够得到关于数组 $A[i]$ 的一个性质：$i < j$ 时，$A[i] < A[j]$
- maxLen 变量记录当前的最长递增子序列的长度。
- 上述的更新规则就转变成对 $A[1, 2, i, maxLen]$ 数组进行更新。
  - $A[1, 2, i, maxLen]$ 是有序的
  - 更新操作只需要进行替换而不需要挪动——也就是说，我们可以使用二分查找，将每个 $idx$ 元素对 $A[1, 2, i, maxLen]$ 数组的更新时间优化到 $O(logN)$（不需要 $O(N)$ 了），算法的时间复杂度就降低到了$O(N logN)$

/*
 * finds a minimum value greater than findingNum in findingArray[1, 2, ..., findingArraySize] and returns its position
 *  findingArray should be in order
 */
int binarySearch(int* findingArray, int findingArraySize, int findingNum) {
    int begin = 1;
    int end = findingArraySize;
    while(begin <= end) {
        int mid = begin + (end - begin)/2;
        if(findingArray[mid] > findingNum) {
            end = mid - 1;
        }
        else if(findingArray[mid] < findingNum) {
            begin = mid + 1;
        }
        else {
            // return the same value position for covering
            return mid;
        }
    }
    // return postion to insert after
    return begin;
}

int lengthOfLIS(int* nums, int numsSize) {
    // sanity check
    if(numsSize < 1) {
        return 0;
    }
    
    // A[i=1, 2, ..., maxLen]: the minimum value of the end element of the i-length increasing sequence
    int A[numsSize+1];
    int maxLen;
    
    maxLen = 1;
    A[1] = nums[0];
    
    for(int idx=1; idx<numsSize; idx++) {
        if(nums[idx] > A[maxLen]) {
            maxLen += 1;
            A[maxLen] = nums[idx];
        }
        else {
            int pos = binarySearch(A, maxLen, nums[idx]);
            A[pos] = nums[idx];
        }
    }
    return maxLen;
}

复杂度从 $O(N^2)$ 缩小到 $O(N logN)$，运行效率得到较大的提升。

提取最长递增子序列

规约为图的最长路径问题
- 利用 $prev[numsSize]$ 数组记录每个最长路径 $L[idx]$ 的前驱节点元素下标 $prev[idx]$，通过 $prev[idx]$ 迭代还原出最长路径。
- 具体实现与下面的动态规划类似。

动态规划

// int totalMaxIdx = <idx for toalMax element index>;
cout << nums[totalMaxIdx];
int prevIdx = prev[totalMaxIdx];
while(prevIdx != -1) {
  cout << " " << nums[prevIdx];
  prevIdx = prev[prevIdx];
}
cout << endl;

耐心排序法
- $A[i=1, 2, …, maxLen]$ 就是满足要求的最长递增子序列。

本文标题:算法设计与分析[0010] Longest Increasing Subsequence（最长递增子序列）

文章作者:Gary

发布时间:2017-04-28, 14:00:22

最后更新:2020-03-28, 12:37:22

原始链接:http://durant35.github.io/2017/04/28/Algorithms_LongestIncreasingSubsequence/

300. Longest Increasing Subsequence

转化为图的最长路径问题（$O(N^2)$）

动态规划（$O(N^2)$）

耐心排序法（$O(N logN)$）

提取最长递增子序列