300. 最长递增子序列

动态规划

func lengthOfLIS(_ nums: [Int]) -> Int {
        
        let len = nums.count
        if len < 2 {
            return 1
        }
        var dp = Array.init(repeating: 0, count: len), maxCount = 0
        for i in 0..<len {
            dp[i] = 1
            for j in 0..<i {
                if nums[i] <= nums[j] {
                    continue
                    
                }else {
                    
                    dp[i] = max(dp[i],dp[j] + 1)
                }
            }
            maxCount = max(maxCount, dp[i])
        }
        return maxCount
    
    }

牌顶排队

func lengthOfLIS(_ nums: [Int]) -> Int {
        
        var array = Array<Int>()
        for num in nums {
            if array.isEmpty {
                array.append(num)
            }else {
                
                var exit = false
                let len = array.count
                for j in 0..<len {
                    
                    if array[j] >= num  {
                        array[j] = num
                        exit = true
                        break
                    }
                    
                }
                if exit == false {
                    
                    array.append(num)
                }
                
            }

        }
        
        return array.count
    
    }

针对上边的数组。。发现是升序的。所以可以用二分查找优化

func lengthOfLIS(_ nums: [Int]) -> Int {
        
        var array = Array.init(repeating: 0, count: nums.count + 1)
        var len = 0
        for num in nums {
            if array.isEmpty {
                array.append(num)
            }else {
              var begin = 0 ,end = len
                while begin < end {
                    let mid = (begin + end ) >> 1
                    if num > array[mid] {
                        begin = mid + 1
                    }else {
                        end = mid
                    }
                }
                array[begin] = num
                if begin == len {
                    len += 1
                }
                
            }
            
        }
        
        return len
    
    }