[LeetCode] 673. Number of Longest Increasing Subsequence

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

Number of Longest Increasing Subsequence - LeetCode

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

 

정수 배열 nums가 있다. 가장 긴 오름차순의 부분배열의 수를 구하시오.

단, 다음 수가 이전 수보다 엄밀히 커야합니다(이상이 아닌 초과)

 

풀이

개수를 저장할 배열 counts와 길이를 저장할 배열 lengths를 만듭니다.  

이중 반복문을 만들어서

      nums를 탐색하며 i번째 수보다 앞에 있는 수들을 탐색하면서 현재 수가 이전 수들의 다음이 될 수 있는지 확인하고, 

     가능하면 이전의 최대길이와 현재의 최대길이를 비교하며 업데이트해줍니다.

안쪽 반복문이 끝나면 최대 길이를 업데이트합니다.

nums 순회가 끝나면 다시 nums를 순회하면서 최대 길이를 가졌다면 정답의 개수를 1씩 늘려줍니다.

 

코드(C++)

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        const int n = nums.size();
        if(n == 0) return 0;
        
        vector<int> lengths(n , 1), counts(n, 1);
        int maxLength = 1;
        int answer = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(lengths[j] + 1 > lengths[i]) {
                        lengths[i] = lengths[j] + 1;
                        counts[i] = counts[j];
                    } else if(lengths[j] + 1 == lengths[i]) {
                        counts[i] += counts[j];
                    }
                }
            }
            maxLength = max(maxLength, lengths[i]);
        }

        for(int i = 0; i < n; i++){
            if(lengths[i] == maxLength) {
                answer += counts[i];
            }
        }
        
        return answer;
    }
};