300. 最长上升子序列
给定一个无序的整数数组, 找到其中最长上升子序列的长度.
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101], 它的长度是 4.
说明:
可能会有多种最长上升子序列的组合, 你只需要输出对应的长度即可.
你算法的时间复杂度应该为 O(n2) .
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
题解
采用动态规划算法: d[i]=d[j]+1 if j<i&&nums[j]<nums[i]
- func lengthOfLIS(nums []int) int {
- var length = len(nums)
- if length<=1{
- return length
- }
- var d = make([]int,length)
- d[0]=1
- var max =d[0]
- for i:=1;i<length;i++{
- d[i]=1
- for j:=0;j<i;j++{
- if nums[j]<nums[i]{
- if d[i]<d[j]+1{
- d[i]=d[j]+1
- }
- }
- }
- if max<d[i]{
- max=d[i]
- }
- }
- return max
- }
来源: http://www.bubuko.com/infodetail-3461293.html