673. Number of Longest Increasing Subsequence

풀이 1. O(N^2) DP

DP에는 해당인덱스를 포함한 LIS 길이를 저장하고,
count에는 그 LIS와 같은 길이의 LIS가 몇개가 있는지 저장한다.

max에는 가장 긴 LIS 길이를 저장하고, 이 LIS길이를 가지고 있는 인덱스의 count의 총합이 정답이 된다.

count의 총 합을 정답으로 하는것을 잊지말자. 3가지의 오답이 나와었다.

• [1,2,4,3,5,4,7,2]
  현재 인덱스와 LIS가 1개차이나면서 LIS로 이어질수있는 값을 만나면, 그 값의 count값을 흡수해야한다.

• [1,1,1,2,2,2,3,3,3], [1,2,3,1,2,3,1,2,3]
  정답로직에 최대LIS를 가진 값들의 count총합을 구하지않아서 오답처리됨.

Time, Space

일단 이중반복문을 통해 처리하므로 Time O(N^2)가 소요되고, dp와 count어레이를 사용하므로 O(N)의 공간이 소요된다.

var findNumberOfLIS = function(nums) {
    const dp=Array(nums.length).fill(1);
    const count=Array(nums.length).fill(1);
    let max = 0;
    let ans = 0;
    
    for(let i=nums.length-1; i>=0; i--){
        for(let j=i+1; j<nums.length; j++){
            if(nums[i]>=nums[j]) continue;
            
            if(dp[i] === dp[j]+1) count[i]+=count[j];
            else if(dp[i] < dp[j]+1){
                dp[i] = dp[j]+1;
                count[i] = count[j];
            }
        }
        max=Math.max(max, dp[i]);
    }
  
    for(let i=0; i<dp.length; i++){
        if(dp[i]===max) ans+=count[i];
    }
    return ans;
};

찾아보니 time을 O(NlogN)로 줄일수있는 방법이 있다고해서 공부한 후 추가할 예정

ref:
https://leetcode.com/problems/number-of-longest-increasing-subsequence/discuss/107295/9ms-C%2B%2B-Explanation%3A-DP-%2B-Binary-search-%2B-prefix-sums-O(NlogN)-time-O(N)-space