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 with nums[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.