Daily LeetCode Challenge - 673. Number of Longest Increasing Subsequence

Problem From.

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

오늘 문제는 주어진 nums 배열에서 오름차순으로 배열되어있는 subsequence 의 갯수를 구하는 문제였다.

이 문제는 dp 를 이용해서 풀 수 있었는데, 각각의 원소를 검사해나가면서, 먼저 dp 배열에 오름차순으로 배열된 리스트를 추가해나간다.
그리고 다음 원소를 추가할때, 다음으로 높은 원소를 검사하면서 dp 배열에서 불러와서 다음 칸에 저장해나가는 식으로 문제를 풀었다.
그런 다음 마지막으로 dp 배열을 보면서 해당하는 원소가 몇개인지 세어주었다.

class Solution {
    fun findNumberOfLIS(nums: IntArray): Int {
        val dp = Array(nums.size) { Pair() }
        for (i in 1 until nums.size) {
            for (j in 0 until i) {
                if (nums[j] >= nums[i]) continue
                val candidateLen = dp[j].longestLen + 1
                if (candidateLen == dp[i].longestLen) {
                    dp[i].combi += dp[j].combi
                } else if (candidateLen > dp[i].longestLen) {
                    dp[i].longestLen = candidateLen
                    dp[i].combi = dp[j].combi
                }
            }
        }
        var longestLen = 0
        var answer = 0
        dp.forEach {
            if (it.longestLen == longestLen) {
                answer += it.combi
            } else if (it.longestLen > longestLen) {
                longestLen = it.longestLen
                answer = it.combi
            }
        }
        return answer
    }
}

data class Pair(var longestLen: Int = 1, var combi: Int = 1)