Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Example 1:
Input: nums = [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: nums = [2,2,2,2,2] Output: 5 Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.
Constraints:
1 <= nums.length <= 2000-106 <= nums[i] <= 106This 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.
This C function initializes two arrays, lengths and counts, with size corresponding to the input nums. It uses nested loops to compare elements, updating these arrays based on the conditions discussed. The overall length and count logic is surrounded by careful checks to decide whether to extend, begin, or merge subsequences.
C++
Java
Python
C#
JavaScript
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.
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300 • NeetCode • 432,482 views views
Watch 9 more video solutions →Practice Number of Longest Increasing Subsequence with our built-in code editor and test cases.
Practice on FleetCode