Sponsored
Sponsored
This approach utilizes two arrays to track the length of the longest increasing subsequence ending at each index and the count of such subsequences. The first array, lengths, will store the length of L.I.S. ending at each position, and the second array, counts, will store how many times such a subsequence appears. We iterate through each possible pair of indices to update these arrays accordingly.
Time Complexity: O(n^2) where n is the number of elements in the input array.
Space Complexity: O(n) used for the lengths and counts arrays.
1#include <vector>
2#include <iostream>
3using namespace std;
4
5int findNumberOfLIS(vector<int>& nums) {
6 int n = nums.size();
7 if (n <= 0) return 0;
8
9 vector<int> lengths(n, 1);
10 vector<int> counts(n, 1);
11
12 int maxLen = 0, result = 0;
13
14 for (int i = 0; i < n; ++i) {
15 for (int j = 0; j < i; ++j) {
16 if (nums[i] > nums[j]) {
17 if (lengths[j] + 1 > lengths[i]) {
18 lengths[i] = lengths[j] + 1;
19 counts[i] = counts[j];
20 } else if (lengths[j] + 1 == lengths[i]) {
21 counts[i] += counts[j];
22 }
23 }
24 }
25 if (lengths[i] > maxLen) {
26 maxLen = lengths[i];
27 result = counts[i];
28 } else if (lengths[i] == maxLen) {
29 result += counts[i];
30 }
31 }
32
33 return result;
34}
35
36int main() {
37 vector<int> nums = {1, 3, 5, 4, 7};
38 cout << findNumberOfLIS(nums) << endl;
39 return 0;
40}This C++ solution follows the same logic as the above C solution but uses C++ standard library features to manage the arrays for readability and convenience. The same nested loop structure updates the arrays based on comparisons.