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.
1function findNumberOfLIS(nums) {
2 const n = nums.length;
3 if (n <= 0) return 0;
4
5 const lengths = Array(n).fill(1);
6 const counts = Array(n).fill(1);
7
8 let maxLen = 0, result = 0;
9
10 for (let i = 0; i < n; ++i) {
11 for (let j = 0; j < i; ++j) {
12 if (nums[i] > nums[j]) {
13 if (lengths[j] + 1 > lengths[i]) {
14 lengths[i] = lengths[j] + 1;
15 counts[i] = counts[j];
16 } else if (lengths[j] + 1 == lengths[i]) {
17 counts[i] += counts[j];
18 }
19 }
20 }
21 if (lengths[i] > maxLen) {
22 maxLen = lengths[i];
23 result = counts[i];
24 } else if (lengths[i] == maxLen) {
25 result += counts[i];
26 }
27 }
28
29 return result;
30}
31
32console.log(findNumberOfLIS([1, 3, 5, 4, 7]));The JavaScript solution similarly invokes Array(n).fill(1) for initializing arrays, and uses traditional looping constructs to perform updates based on comparisons. JavaScript handles the state and object properties effectively.