Leetcode 673. Number of Longest Increasing Subsequence
Problem Description
Given an unsorted array of integers, we want to find the number of longest increasing subsequences. A subsequence is a sequence that can be derived from the original sequence by deleting any number of elements without changing the order of the remaining elements. The longest increasing subsequence is the longest subsequence that is increasing, i.e., each element is larger than the previous one.
For example, given the input array [1,3,5,4,7], the two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7], so the output would be 2. If the input array is [2,2,2,2,2], the longest increasing subsequence is simply any of the numbers, and since there are 5 numbers, the output is 5.
Approach
The solution uses dynamic programming. It scans through the input array, maintaining two arrays: length
and count
. At each position i
in the input:
-
length[i]
is the length of the longest increasing subsequence that ends withnums[i]
. -
count[i]
is the number of such subsequences.
When we process a new number, we scan through all positions j
before it. If nums[j]
is less than the number, that is, it can be appended to an increasing subsequence ending with nums[j]
, we update our length
and count
arrays.
When we process each number, we also keep track of maxLength
, the longest length we have seen, and ans
, the total number of such sequences.
Let's walk through an example:
Input: [1,3,5,4,7]
At the start: length = [1, 1, 1, 1, 1]
, count = [1, 1, 1, 1, 1]
, maxLength = 0
, ans = 0
.
After processing 3: length = [1, 2, 1, 1, 1]
, count = [1, 1, 1, 1, 1]
, maxLength = 2
, ans = 1
.
After processing 5: length = [1, 2, 3, 1, 1]
, count = [1, 1, 1, 1, 1]
, maxLength = 3
, ans = 1
.
After processing 4: length = [1, 2, 3, 3, 1]
, count = [1, 1, 1, 1, 1]
, maxLength = 3
, ans = 2
.
After processing 7: length = [1, 2, 3, 3, 4]
, count = [1, 1, 1, 1, 2]
, maxLength = 4
, ans = 2
.
If we look at the final state, we can see that there are 2 length-4 increasing subsequences, so the answer is 2.
Python Solution
1 2python 3class Solution: 4 def findNumberOfLIS(self, nums): 5 n = len(nums) 6 if n <= 1: 7 return n 8 lengths = [1] * n 9 counts = [1] * n 10 11 for i in range(n): 12 for j in range(i): 13 if nums[i] > nums[j]: 14 if lengths[j] + 1 > lengths[i]: 15 lengths[i] = lengths[j] + 1 16 counts[i] = counts[j] 17 elif lengths[j] + 1 == lengths[i]: 18 counts[i] += counts[j] 19 20 longest = max(lengths) 21 return sum(c for l, c in zip(lengths, counts) if l == longest)
Java Solution
1 2java 3class Solution { 4 public int findNumberOfLIS(int[] nums) { 5 int n = nums.length; 6 if (n <= 1) return n; 7 int[] lengths = new int[n]; 8 int[] counts = new int[n]; 9 Arrays.fill(lengths, 1); 10 Arrays.fill(counts, 1); 11 12 for (int i = 0; i < n; i++) { 13 for (int j = 0; j < i; j++) { 14 if (nums[i] > nums[j]) { 15 if (lengths[j] + 1 > lengths[i]) { 16 lengths[i] = lengths[j] + 1; 17 counts[i] = counts[j]; 18 } else if (lengths[j] + 1 == lengths[i]) { 19 counts[i] += counts[j]; 20 } 21 } 22 } 23 } 24 25 int longest = 0, ans = 0; 26 for (int length: lengths) { 27 longest = Math.max(longest, length); 28 } 29 for (int i = 0; i < n; i++) { 30 if (lengths[i] == longest) ans += counts[i]; 31 } 32 return ans; 33 } 34}
JavaScript Solution
1 2 JavaScript 3var findNumberOfLIS = function(nums) { 4 let n = nums.length; 5 if (n <= 1) { 6 return n; 7 } 8 let lengths = new Array(n).fill(1); 9 let counts = new Array(n).fill(1); 10 11 for (let i = 0; i < n; i++) { 12 for (let j = 0; j < i; j++) { 13 if (nums[i] > nums[j]) { 14 if (lengths[j] + 1 > lengths[i]) { 15 lengths[i] = lengths[j] + 1; 16 counts[i] = counts[j]; 17 } else if (lengths[j] + 1 == lengths[i]) { 18 counts[i] += counts[j]; 19 } 20 } 21 } 22 } 23 24 let longest = Math.max(...lengths); 25 return counts.reduce((acc, count, i) => lengths[i] === longest ? acc + count : acc, 0); 26};
In our JavaScript implementation, we follow the same approach as in the other languages. We create arrays to store the lengths and counts, and initialize each element to 1, since each number by itself is a valid increasing subsequence with length 1. Then, we iterate through each pair of numbers, comparing each number to all previous numbers in the array. If a larger number is found, we update our lengths and counts accordingly. Finally, we return the sum of counts which have the length equal to the maximum length. We use the reduce
method for this final calculation. Note the use of the spread operator (...
) in the Math.max()
function to get the maximum value from an array instead of multiple numbers.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.