Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 21

Description

Number of Longest Increasing Subsequence

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

Notice that the sequence has to be strictly increasing.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 2000
• -106 <= nums[i] <= 106

Solution

class Solution {
public:
  int findNumberOfLIS(vector<int>& nums) {
    if(nums.empty()) return 0;
    vector<int> LIS(nums.size(), 1);
    vector<int> ways(nums.size(), 1);
    for(int i = 1; i < nums.size(); ++i) {
      for(int j = 0; j < i; ++j) {
        if(nums[j] < nums[i] && LIS[j]+1 > LIS[i]) {
          ways[i] = ways[j];
          LIS[i] = LIS[j] + 1;
        } else if(nums[j] < nums[i] && LIS[j]+1 == LIS[i]) {
          ways[i] += ways[j];  
        } 
      }
    }
    int LISLength = *max_element(LIS.begin(), LIS.end());
    int ans = 0;
    for(int i = 0; i < nums.size(); ++i) {
      if(LIS[i] == LISLength) ans += ways[i];
    }
    return ans;
  }
};

// Accepted
// 223/223 cases passed (217 ms)
// Your runtime beats 43.24 % of cpp submissions
// Your memory usage beats 66.65 % of cpp submissions (13.2 MB)