# 673. Number of Longest Increasing Subsequence

• Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public: int findNumberOfLIS(vector& nums) { const int n = nums.size(); int ans = 0; int maxLength = 0; vector length(n, 1); // length[i] := LIS's length ending w/ nums[i] vector count(n, 1); // count[i] := # of the LIS ending w/ nums[i] // calculate length and count arrays for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) if (nums[j] < nums[i]) if (length[i] < length[j] + 1) { length[i] = length[j] + 1; count[i] = count[j]; } else if (length[i] == length[j] + 1) { count[i] += count[j]; } // get # of LIS for (int i = 0; i < n; ++i) if (length[i] > maxLength) { maxLength = length[i]; ans = count[i]; } else if (length[i] == maxLength) { ans += count[i]; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public int findNumberOfLIS(int[] nums) { final int n = nums.length; int ans = 0; int maxLength = 0; int[] length = new int[n]; // length[i] := LIS's length ending w/ nums[i] int[] count = new int[n]; // count[i] := # of the LIS ending w/ nums[i] Arrays.fill(length, 1); Arrays.fill(count, 1); // calculate length and count arrays for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) if (nums[j] < nums[i]) if (length[i] < length[j] + 1) { length[i] = length[j] + 1; count[i] = count[j]; } else if (length[i] == length[j] + 1) { count[i] += count[j]; } // get # of LIS for (int i = 0; i < n; ++i) if (length[i] > maxLength) { maxLength = length[i]; ans = count[i]; } else if (length[i] == maxLength) { ans += count[i]; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: ans = 0 maxLength = 0 length = [1] * len(nums) # length[i] := LIS's length ending w/ nums[i] count = [1] * len(nums) # count[i] := # of the LIS ending w/ nums[i] # calculate length and count arrays for i, num in enumerate(nums): for j in range(i): if nums[j] < num: if length[i] < length[j] + 1: length[i] = length[j] + 1 count[i] = count[j] elif length[i] == length[j] + 1: count[i] += count[j] # get # of LIS for i, l in enumerate(length): if l > maxLength: maxLength = l ans = count[i] elif l == maxLength: ans += count[i] return ans