• Time:O(n^2)
• Space:O(n)

## C++

``````class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
int maxLength = 0;
vector<int> length(n, 1);  // length[i] := LIS's length ending w/ nums[i]
vector<int> 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;
}
};
``````

## JAVA

``````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;
}
}
``````

## Python

``````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
``````