300. Longest Increasing Subsequence

题目

Given an unsorted array of integers, find the length of longest increasing subsequence.

题意

给定无序整型数组，求出递增序列长度（该序列不一定连续）

例子

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

题解

解法一 O(n^2)
使用dp的方法，假设F(i)表示0到下标为i的位置为止递增的序列最长长度。所以

for 0<=j<i
if nums[j]<nums[i]
F(i)=max(F(j)+1,F(i))

代码一

func lengthOfLIS(nums []int) int {
    L := len(nums)
    if L==0{
        return 0
    }
    maxLens := make([]int,L)
    max := 0
    
    for i:=0;i<L;i++{
        for j:=0;j<i;j++{
            if nums[i]>nums[j]{
                maxLens[i] = Max(maxLens[j]+1,maxLens[i])
            }
        }
        max = Max(max,maxLens[i]+1)
    }
    return max
}

func Max(m1,m2 int)int{
    if m1>m2{
        return m1
    }
    return m2
}

解法二 O(nlogn)
使用一个数组dp，遍历每个元素，遍历到的元素在dp中进行二分查找，查找第一个大于它的元素，然后替换掉他，如果没有则添加到数组里面，最后返回的dp长度就是结果。

代码二

func lengthOfLIS(nums []int) int {
    L := len(nums)
    if L==0{
        return 0
    }
    dp := make([]int,0)
    for i:=0;i<L;i++{
        left,right := 0,len(dp)
        for left<right{
            mid := (right-left)/2+left
            if dp[mid]<nums[i]{
                left = mid+1
            }else{
                right = mid
            }
        }
        if right>=len(dp){
            dp = append(dp,nums[i])
        }else{
            dp[right] = nums[i]
        }
    }
    return len(dp)   
}

总结

这道题也是子串的类似题目，但是就是一看到题目就没有思路。想过dp，但是不知道具体的求解F的方法。这里的F(i)是需要遍历前面的所有元素的F来确定最大的那个值然后更新到这个F的。能够理解到这一点dp就能做出来了。所以dp并不是当初的取决上一个，有时候去取决与前面所有可能的最值。
第二种做法也是知道了之后觉得非常简单，但是在刚开始看的时候确完全想不出这种思路。受限于遍历两边和之前那种思路，没有扩展开到使用额外的空间来存结果。