Leetcode - Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

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

Example:

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. 

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 || len(nums) == 1 {
        return len(nums)
    }
    
    dp := make([]int, len(nums))
    dp[0] = 1
    for i := 1; i < len(nums); i++ {
        dp[i] = 1
        max := 1
        for j := 0; j < i; j++ {
            var tmp int
            if nums[j] < nums[i] {
                tmp = dp[j] + 1
                if tmp > max {
                    max = tmp
                }
            }
            
        }
        dp[i] = max
    }
    
    max := math.MinInt32
    for _, n := range dp {
        if max < n {
            max = n
        }
    }
    return max
}

• 相关文章
• 全局相关文章