673. Number of Longest Increasing Subsequence

Problem Description

The problem we're given involves an integer array called nums. Our goal is to figure out how many subsequences of this array have the greatest length and are strictly increasing. A subsequence is defined as a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Importantly, the condition here is that our subsequence must be strictly increasing, meaning that each element must be greater than the one before it.

Intuition

To address the problem, we consider a dynamic programming approach that allows us to build up the solution by considering the number of increasing subsequences ending at each element.

We use two arrays, dp and cnt. The dp array will keep track of the length of the longest increasing subsequence that ends with nums[i] for each element i. The cnt array, conversely, records the total number of such subsequences of maximum length ending with nums[i].

We need to iterate over each number in the nums array and, for each element, iterate over all previous elements to check if a longer increasing subsequence can be created. When we find such an element nums[j] that is less than nums[i] (ensuring an increase), we have two cases:

1. If the subsequence ending at nums[j] can be extended by nums[i] to yield a longer subsequence, we update dp[i] and set cnt[i] to be the same as cnt[j] since we have identified a new maximum length.
2. If the extended subsequence has the same length as the current maximum subsequence ending at nums[i], we increase cnt[i] by cnt[j] because we have found an additional subsequence of this maximum length.

As we move through the array, we maintain variables to keep track of the longest subsequence found so far (maxLen) and the number of such subsequences (ans). If a new maximum length is found, maxLen is updated and ans is set to the number of such subsequences up to nums[i]. If we find additional sequences of the same maximum length, we add to ans accordingly.

At the end of the iterations, ans represents the total number of longest increasing subsequences present in the whole array nums.

Learn more about Segment Tree and Dynamic Programming patterns.

Solution Approach

The solution uses a dynamic programming approach, which is a method for solving complex problems by breaking them down into simpler subproblems. It stores the results of these subproblems to avoid redundant work.

Here is a step-by-step breakdown of the approach:

1. Initialize two lists, dp and cnt, both of size n, where n is the length of the input array nums. Each element of dp starts with a value of 1, because the minimum length of an increasing subsequence is 1 (the element itself). Similarly, cnt starts with 1s because there's initially at least one way to have a subsequence of length 1 (again, the element itself).

2. Iterate over the array with two nested loops. The outer loop goes from i = 0 to i = n - 1, iterating through the elements of nums. The inner loop goes from j = 0 to j < i, considering elements prior to i.

3. Within the inner loop, compare the elements at indices j and i. If nums[i] is greater than nums[j], it means nums[i] can potentially extend an increasing subsequence ending at nums[j].

4. Check if the increasing subsequence length at j plus 1 is greater than the current subsequence length at i (dp[j] + 1 > dp[i]). If it is, this means we've found a longer increasing subsequence ending at i, so update dp[i] to dp[j] + 1, and set cnt[i] to cnt[j] because the number of ways to achieve this longer subsequence at i is the same as the number at j.

5. If dp[j] + 1 equals dp[i], it indicates another subsequence of the same maximum length ending at i, so increment cnt[i] by cnt[j].

6. Keep track of the overall longest sequence length found (maxLen) and the number of such sequences (ans). After processing each i, compare dp[i] with maxLen. If dp[i] is greater than maxLen, update maxLen to dp[i] and set ans to cnt[i]. If dp[i] equals maxLen, add cnt[i] to ans.

7. Continue this process until all elements have been considered. At the end, the variable ans will contain the number of longest increasing subsequences in nums.

By using dynamic programming, this solution effectively builds up the increasing subsequences incrementally and keeps track of their counts without having to enumerate each subsequence explicitly, which would be infeasible due to the exponential number of possible subsequences.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose the given integer array nums is [3, 1, 2, 3, 1, 4].

1. We initialize dp and cnt arrays as [1, 1, 1, 1, 1, 1] since each element by itself is a valid subsequence of length 1 and there is at least one way to make a subsequence of one element.

2. Start iterating with i from index 0 to the end of the array, and for each i, we iterate with j from 0 to i-1.

3. When i = 2 (element is 2), we find that nums[2] > nums[0] (2 > 3). However, as 2 is not greater than 3, no updates are done. Then we compare nums[2] with nums[1] (2 > 1), this is true, and since dp[1] + 1 > dp[2], we update dp[2] to dp[1] + 1 = 2, also updating cnt[2] to cnt[1].

4. Moving to i = 3 (element is 3), we compare with all previous elements one by one. For j = 0, nums[3] (3) is not greater than nums[0] (3). For j = 1, nums[3] (3) is greater than nums[1] (1), and dp[1] + 1 > dp[3] so we update dp[3] and cnt[3] to 2. For j = 2, nums[3] (3) is greater than nums[2] (2), and dp[2] + 1 = 3 which is greater than the current dp[3] (2). So we update dp[3] to 3, and cnt[3] to cnt[2].

5. Continue this process for i = 4 and i = 5. When we reach i = 5 (element is 4) and j = 3, since nums[5] (4) is greater than nums[3] (3) and dp[3] + 1 > dp[5] (4 > 1), we update dp[5] to 4, and cnt[5] to cnt[3].

6. We keep track of the maxLen and ans throughout the process. Initially, maxLen is 1 and ans is 6 (because we have six elements, each a subsequence of length 1). After updating all dp[i] and cnt[i], we find maxLen to be 4 (subsequences ending at index 5) and ans will be updated to the count of the longest increasing subsequences ending with nums[5], which in this case is 1.

At the end of this process, the dp array is [1, 1, 2, 3, 1, 4] and the cnt array is [1, 1, 1, 1, 1, 1]. We conclude that the length of the longest increasing subsequence is 4 and the number of such subsequences is 1 (ending with the element 4 in the original array).

This walk-through illuminates the step-by-step application of our dynamic programming solution to find the total number of the longest increasing subsequences present in the array nums.

Solution Implementation

Time and Space Complexity

The given Python function findNumberOfLIS calculates the number of Longest Increasing Subsequences (LIS) in an array of integers. Analyzing the time complexity involves examining the nested loop structure, where the outer loop runs n times (once for each element in the input list nums) and the inner loop runs at most i times for the ith iteration of the outer loop. Consequently, in the worst case, the inner loop executes 1 + 2 + 3 + ... + (n - 1) times, which can be expressed as the sum of the first n-1 natural numbers, resulting in a time complexity of O(n^2).

The space complexity of the function is determined by the additional memory allocated for the dynamic programming arrays dp and cnt, each of size n. Therefore, the space complexity of the function is O(n), which is linear with respect to the size of the input list.

Learn more about how to find time and space complexity quickly using problem constraints.