Leetcode - Number of Longest Increasing Subsequence

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

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

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

func findNumberOfLIS(nums []int) int {
    if len(nums) < 2 {
        return len(nums)
    }
    count := make([]int, len(nums))
    length := make([]int, len(nums))
    count[0] = 1
    length[0] = 1
    maxNum := 1
    result := 0
    for i := 1; i < len(nums); i++ {
        count[i] = 1
        length[i] = 1
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                if length[i] == length[j] + 1 {
                    count[i] += count[j]
                } else if length[i] < length[j] + 1 {
                    length[i] = length[j] + 1
                    count[i] = count[j]
                }
            }
            
        }
        if maxNum < length[i] {
            maxNum = length[i]
        }
    }
    for i := 0; i < len(nums); i++ {
        if length[i] == maxNum {
            result += count[i]
        }
    }
    

    return result
}

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