给定一个长度为 n 的数组 arr,求它的最长严格上升子序列的长度。
所谓子序列,指一个数组删掉一些数(也可以不删)之后,形成的新数组。例如 [1,5,3,7,3] 数组,其子序列有:[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的,当且仅当该序列不存在两个下标 和 满足 且 。
数据范围:
要求:时间复杂度 , 空间复杂度
[6,3,1,5,2,3,7]
4
该数组最长上升子序列为 [1,2,3,7] ,长度为4
#define max(a,b) (a>b?a:b) int LIS(int* arr, int arrLen ) { int dp[1000]={1}, res=1, i, j; if(arrLen==0) return 0; for(i=0; i<sizeof(dp)/sizeof(int); i++) dp[i] = 1; for(i=1; i<arrLen; i++) { for(j=0; j<i; j++) { if(arr[i]>arr[j]) { dp[i] = max(dp[i], dp[j]+1); res = max(res, dp[i]); } } } return res; }