[LeetCode] 673. Number of Longest Increasing Subsequence

😎풀이

1. 인덱스 별 최장 LIS 길이를 저장하는 dp 배열 선언
2. 인덱스 별 LIS 수를 저장하는 count 배열 선언
3. 요소 순회하며 최장 길이 및 LIS 카운트 갱신
4. 최장 길이에 해당하는 LIS 카운트 반환

function findNumberOfLIS(nums: number[]): number {
    const n = nums.length
    if(n <= 1) return n
    const dp = Array.from({ length: n }, () => 1)
    const count = Array.from({ length: n }, () => 1)
    let longest = 0
    let lis = 0
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < i; j++) {
            if(nums[i] <= nums[j]) continue
            if(dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1
                count[i] = count[j]
            } else if(dp[i] === dp[j] + 1) {
                count[i] += count[j]
            }
        }
        longest = Math.max(longest, dp[i])
    }
    for(let i = 0; i < n; i++) {
        if(dp[i] !== longest) continue
        lis += count[i]
    }
    return lis
};