leetcode_300

Golang:

思路：用一个数组arr，arr[i]表示以nums中以i为下标的元素所构成的最长上升子序列的长度，举个例子：[1,3,6,7,9,4,10,5,6]，i=4时，即nums[i]=9，则arr[4]表示的是9作为最长上升子序列的最后一位时，这个序列的最大长度。最后，遍历这个数组arr，看下最大值，那么就是最长上升子序列的长度。

代码如下：

func lengthOfLIS(nums []int) int {
    if len(nums)<=1 {
        return len(nums)
    }
    arr:=make([]int,len(nums))
    arr[0]=1
    res:=1
    for i:=1;i<len(arr);i++{
        arr[i]=1
        for j:=0;j<i;j++{
            if nums[i]>nums[j]&&arr[j]+1>arr[i] {
                arr[i]=arr[j]+1
            }
        }
        if arr[i]>res {
            res=arr[i]
        }
    }
    return res
}

有疑问加站长微信联系（非本文作者）