300. 最长上升子序列
题目
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
思路
代码
public int lengthOfLIS(int[] nums
) {
int n
= nums
.length
;
int f
[] = new int[n
+1];
if(n
==0){
return 0;
}
f
[1] = 1;
int res
= 0;
Arrays
.fill(f
, 1);
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<i
;j
++){
if(nums
[i
-1]>nums
[j
-1]){
f
[i
] = Math
.max(f
[j
]+1,f
[i
]);
}
}
res
= Math
.max(res
,f
[i
]);
}
return res
;
}
优化
见方法二 https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
