最长上升子序列算法（详细讲解+多个版本实现（C/C++和Python））

1. 什么是最长上升子序列（LIS）问题？
   【题目描述】
   给定N个数，求这N个数的最长上升子序列的长度。
   【样例输入】
   7
   2 5 3 4 1 7 6
   【样例输出】
   4
   什么是最长上升子序列？ 就是给你一个序列，请你在其中求出一段不断严格上升的部分，它不一定要连续。
   就像这样：2,3,4,7和2,3,4,6就是序列2 5 3 4 1 7 6的两种选取方案。最长的长度是4.
   更直接的描述：
   
2. 首先需要设计状态，以及状态转移方程
   
3. 状态转移方程的推导
   
4. 状态转移方程的详细推导
   
5. C代码实现
   
6. 总结

7. C++两种方法代码实现：

第一种方法：单纯的DP算法实现（复杂度O(N2)）

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        if (nums.size() == 0)
            return 0;
        vector<int> dp(nums.size(), 0);
        dp[0] = 1;
        int maxLIS = 1;
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
                maxLIS = max(dp[i], maxLIS);
            }
        }
        return maxLIS;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第二种方法：使用栈和二分优化（复杂度Ologn）

class Solution {
  public:
    int binary_search(int num, vector<int> &st) {
        int low = 0, high = st.size() - 1, mid;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (st[mid] == num)
                return mid;
            else if (st[mid] > num)
                high = mid - 1;
            else if (st[mid] < num)
                low = mid + 1;
        }
        return low;
    }
    int lengthOfLIS(vector<int> &nums) {
        vector<int> st;
        if (nums.size() == 0)
            return 0;
        st.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > st.back())
                st.push_back(nums[i]);
            else {
                int pos = binary_search(nums[i], st);
                st[pos] = nums[i];
            }
        }
        return st.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

8. Python实现

Python版本一：

def lis(arr):
    n = len(arr)
    m = [0]*n
    for x in range(n-2, -1, -1): #这里是逆序，所以和C++部分不一样
        for y in range(n-1, x, -1): #这里是逆序，所以和C++部分不一样
            if arr[x] < arr[y] and m[x] <= m[y]:
                m[x] +=1 #此部分和C++版本的也不一样，如果是顺序，调过来就行了，和C++版本类似
        max_value = max(m)
        '''
        #这一部分是打印排序的最长子序列结果，如果需要将注释打开就行
        result = []
        for i in range(n):
            if m[i] == max_value:
                result.append(arr[i])
                max_value -=1
        '''
    return max_value

arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(lis(arr))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Python版本二：

def lis(arr):
    n = len(arr)
    m = [0]*n    
    for i in range(n): 
        for j in range(i):
            if (arr[j] < arr[i]):
                m[i] = max(m[i],m[j]+1)
            #m[i] = max(m[i], m[j]+1)
        max_value = max(m)           
        result = []        
        for x in range(n-1,-1,-1): 
        #按道理说range(n-1,-1,-1)和range(0,n,1)表达的意思是一样，但是得出结果不一样，因为下面还有输出递减，需要从大到小的顺序。
            if max_value == m[x]:
                result.append(arr[x])
                max_value -= 1
    return result 
    
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(lis(arr))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

参考文献：

1. https://www.bilibili.com/video/BV1KK4y1e7t7/?spm_id_from=autoNext
2. https://www.jianshu.com/p/410e22094c40
3. https://www.cnblogs.com/frankchenfu/p/7107019.html
4. https://www.runoob.com/w3cnote/python-longest-increasing-subsequence.html