这篇文章继续介绍使用动态规划法解决LIS问题的方法。

LIS：最长上升子序列

LIS（最长上升子序列）: Longest Increasing Subsequence的缩写，指的是一个序列中最长的单调递增的子序列。

• 题目内容说明：求长度为n数列中的最长的上升子序列的长度。

定义DP数组

鉴于上述说明过于简略，这里借一张图来说明问题以及解决的思路

最简单的方式是使用同等长度的dp数组来解决问题，dp数组的具体含义如下：

dp[i]: 待求解数列中以第i个元素为结尾的最长上升子序列的长度。

求解方法

求解方法：如果第i-j个数字都比第i个大，dp[i]为1，如果比之前有比其大的，就在此基础上寻取最大解，所以就是一个两重循环进行问题的解决，所以没有优化的情况下，复杂度为n平方。

代码模拟

#include <stdio.h>
#include <stdlib.h>int max(int x, int y) {return x > y ? x : y;
}int get_lis(int* arr, int num) {int* dp = malloc(sizeof(int) * num);int  max_len = dp[0];for (int i=0; i<num; i++) {dp[i]=1;for (int j=0; j<i; j++) {if (arr[i] > arr[j]) dp[i] = max(dp[i],dp[j]+1);}}for(int i=0; i<num; i++) max_len = max(max_len,dp[i]);free(dp); dp=NULL;return max_len;
}int main(){int n = 0;while(scanf("%d",&n) != EOF) {int* array = (int *)malloc(sizeof(int) * n);for (int i=0; i<n; i++) scanf("%d",&array[i]);printf("%d\n",get_lis(array,n));free(array); array = NULL;}return 0;
}

示例执行结果如下：

8
10 9 2 5 3 7 21 18
4

总结

使用动态规划数组即可解决LIS的方式，但是n平方的复杂度实际上结合二分查找可以降到nlogn的程度，然后是否滚动数组是否可以使用，以及很多组合的方式都可能会出现，都是值得进一步思考的。