Skip to main content

673. Number of Longest Increasing Subsequence

medium

Count how many strictly-increasing subsequences achieve the maximum length. The LIS pattern with a parallel count array tracking ties.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing.

Constraints

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Run the O(n^2) LIS DP but keep a parallel count[i] = number of LIS ending at i.

Hint 2

When dp[j] + 1 > dp[i] set dp[i] = dp[j] + 1 and count[i] = count[j]. On equal, add: count[i] += count[j].

Hint 3

Sum count[i] over all i where dp[i] equals the global max length.

Solution approach

Reveal approach

Two parallel 1D arrays. dp[i] = length of the longest strictly-increasing subsequence ending at index i. count[i] = the number of such longest subsequences ending at i. Initialize dp[i] = 1 and count[i] = 1. For i from 0 to n-1 and j from 0 to i-1: if nums[j] < nums[i], compare dp[j] + 1 to dp[i]. If strictly greater, set dp[i] = dp[j] + 1 and count[i] = count[j] (replace). If equal, count[i] += count[j] (merge). Find max_len = max(dp). Return sum of count[i] over indices where dp[i] == max_len. O(n^2) time, O(n) space.

Complexity

Time
O(n^2)
Space
O(n)

Related patterns

  • dynamic-programming
  • lis

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

More DP 1D practice problems

See all DP 1D problems →