Number of Longest Increasing Subsequence

“Number of Longest Increasing Subsequence” involves finding not just the length of the longest increasing subsequence, but also how many such subsequences exist.

This can be associated with two other problems:

“Longest Increasing Subsequence” is a simpler problem and forms an approximate isomorphism. This problem only asks for the length of the longest increasing subsequence. In the “Number of Longest Increasing Subsequence” problem, we build upon this by also counting the number of such longest subsequences.
“Russian Doll Envelopes” is a more complex problem that can be mapped to “Number of Longest Increasing Subsequence”. In this problem, you need to find the maximum number of envelopes you can put one inside another. It’s essentially a variant of longest increasing subsequence but in two dimensions, so it adds complexity.

The order of complexity, from simple to more complex, is:

“Longest Increasing Subsequence”
“Number of Longest Increasing Subsequence”
“Russian Doll Envelopes”.

Each problem is focused on finding longest increasing subsequences, but the complexity increases as we go from only needing the length of the longest subsequence, to also counting such subsequences, to handling two dimensions. Hence, they can be viewed as approximate isomorphisms of each other.

10 Prerequisite LeetCode Problems

For “673. Number of Longest Increasing Subsequence”, the following are a good preparation:

“300. Longest Increasing Subsequence” - This problem forms the basis for the given problem as you have to find the length of the longest increasing subsequence in a given array. This problem provides practice for the core concept of tracking increasing subsequences.
“674. Longest Continuous Increasing Subsequence” - Similar to problem 300 but here you’re finding continuous increasing subsequences. This introduces the additional complexity of continuity, which is a useful concept to understand.
“354. Russian Doll Envelopes” - Here, the challenge is to find the maximum number of envelopes that can be put one inside other. It’s an extension of the longest increasing subsequence problem, where sorting and dynamic programming are used.
“646. Maximum Length of Pair Chain” - This problem is another variant of longest increasing subsequences, but with pairs of numbers. It helps practice the concept with a slight twist.
“376. Wiggle Subsequence” - This problem requires you to find the longest subsequence with alternating increase and decrease. It is not strictly similar, but knowing how to handle alternating sequences can help build a deeper understanding of subsequences.
“53. Maximum Subarray” - This problem, while not strictly about increasing subsequences, helps to develop understanding of how to track and build subsequences for maximum value, which is a related concept.
“1143. Longest Common Subsequence” - In this problem, you find the longest common subsequence in two given strings, which helps you practice subsequence problems and dynamic programming.
“392. Is Subsequence” - A simpler problem that checks if one string is a subsequence of another. It helps understand the basic concept of a subsequence.
“198. House Robber” - In this problem, the robber can’t rob two consecutive houses, so you have to find the subsequence with maximum sum, which indirectly relates to the increasing subsequence problem.
“1395. Count Number of Teams” - This problem is about counting increasing or decreasing subsequences of length 3. It is a simpler version of the problem where you’re counting subsequences of a particular length.

These problems are good preparation before solving the current problem “Number of Longest Increasing Subsequence”. Here’s why:

Largest Divisible Subset: This problem is similar because it involves finding a subset of numbers that all meet a certain condition (in this case, being divisible by each other), and it asks for the largest such subset. This involves the understanding of dynamic programming in terms of storing previous computations and understanding how the problem can be broken down into subproblems (a key element of dynamic programming).
Delete and Earn: In this problem, you are tasked with choosing numbers from an array to maximize a score, but with the constraint that choosing a number eliminates the ability to choose certain other numbers. This requires thinking about the implications of each choice you make, much like in the longest increasing subsequence problem. Understanding how choices affect future possibilities is crucial in many dynamic programming problems.
Longest String Chain: This problem involves finding the longest possible sequence of strings where each string can be made from the previous one by adding a single character. This problem is similar to the longest increasing subsequence problem because it requires you to think about sequences and how one element can build off the last. This problem also emphasizes on building solutions through subproblems which is a hallmark of dynamic programming.

All these train you in a similar way of thinking - considering each element’s impact on the overall sequence or set, and using dynamic programming to break down complex problems into simpler subproblems. So they are indeed good preparation for solving the “Number of Longest Increasing Subsequence” problem. Each of these problems in some way introduces, reinforces or extends the concept of tracking, building or using subsequences within a larger sequence, which is crucial for solving problem 673.

Problem Classification

The problem can be categorized into Dynamic Programming because this type of problem often relies on solving overlapping subproblems and building up to the final solution.

The ‘What’ components of the problem are as follows:

The problem provides an integer array called nums.
We are asked to determine the number of longest increasing subsequences in the given array.
An increasing subsequence is defined as a subsequence where each element is strictly greater than the previous one.
The input array size can range from 1 to 2000, and the values it holds can range from -10^6 to 10^6.

This problem can be classified as a Counting problem where we need to count the number of longest increasing subsequences. Since we likely need to track each element’s effect on the possible subsequences, it’s also a Sequence or Order-related problem. The use of Dynamic Programming techniques may be necessary because the solution likely involves deriving the answer for a larger problem by combining the solutions to smaller subproblems.

Identifying Problem Isomorphism

Isomorphism involves finding a similar structure in a different context. For this problem, we are trying to find the longest increasing subsequences within an array of integers. This concept can be isomorphic to several real-world scenarios. Here are a couple of examples:

Growth Analysis: Consider an array representing the growth of a plant (in inches) over time. Each element of the array is the height of the plant on a given day. In this case, a strictly increasing subsequence represents a period of time when the plant was consistently growing. The longest increasing subsequence can represent the longest growth period of the plant, and the number of such subsequences can represent the number of such growth periods.
Stock Market Analysis: Another isomorphism can be found in the financial domain. The array could represent the closing price of a stock on consecutive days. An increasing subsequence would represent a bullish (upward) trend. The problem of finding the longest increasing subsequences can be interpreted as finding the longest bullish trends in the stock’s history and the number of such trends.

In both cases, we map an array of integers to a sequence of observations and translate the longest increasing subsequence problem to finding trends or patterns in these sequences.

Although these are useful analogies, the mathematical complexity and nuances of the original problem might not fully translate into these isomorphic scenarios.

“Longest Increasing Subsequence” and “Russian Doll Envelopes”, can be considered as related or similar problems to “Number of Longest Increasing Subsequence”, but they are not exact equivalents or isomorphisms.

They all deal with the concept of finding increasing subsequences in a sequence of numbers, which is a common thread between them. They are all typically solved using Dynamic Programming, indicating a similarity in their underlying problem-solving approaches.

However, they aren’t exact equivalents because they have unique aspects not shared by the others:

Problem 300 asks for the length of the longest strictly increasing subsequence in a sequence but doesn’t concern itself with the count of such subsequences.
Problem 354 extends the concept to two dimensions (width and height of envelopes) and seeks to find the maximum number of envelopes you can Russian doll (one envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope).
Problem 673 uniquely asks for the count of the longest increasing subsequences in the sequence, a detail not required by the other two problems.

So, while they share a thematic connection and might use similar problem-solving strategies, they are not exact equivalents or isomorphisms of each other.

“Number of Longest Increasing Subsequence”, can be viewed as a variation of LeetCode problem 300, “Longest Increasing Subsequence”.

The task in problem 300 is to find the length of the longest increasing subsequence. This is a simpler problem than 673, which not only requires finding the longest increasing subsequence but also the number of such subsequences.

Thus, while both problems deal with finding increasing subsequences in a given sequence, problem 673 adds an additional layer of complexity by requiring the count of these subsequences, making it a more complex variation of problem 300. The techniques used to solve problem 300 can form the basis for solving problem 673, but additional steps would need to be added to handle the counting aspect.

The identification comes from observing the structure and requirements of both problems. Let’s compare the two problems:

LeetCode problem 300, “Longest Increasing Subsequence”, asks for the length of the longest strictly increasing subsequence in a given array of integers. This is a classic dynamic programming problem.
LeetCode problem 673, “Number of Longest Increasing Subsequence”, asks not just for the length of the longest strictly increasing subsequence, but also for the count of all such longest subsequences. This is essentially an extension or a variation of the problem 300, as it has an extra requirement on top of finding the longest increasing subsequence.

In essence, problem 673 has all the elements of problem 300, but with an added complexity. That’s why we can say that problem 673 is a variation of problem 300. Any approach to solve problem 673 will likely have to solve the “Longest Increasing Subsequence” problem as a sub-problem or an intermediate step, but it also needs an additional mechanism to keep track of the count of such subsequences.

Clarification Questions

Subsequence Definition: Can we confirm that by ‘subsequence’, we mean a sequence that can be derived from the original array by deleting some or no elements without changing the order of the remaining elements?
Strictly Increasing Definition: When the problem says ‘strictly increasing’, it means each number in the sequence must be larger than the one before it, correct? (i.e., it’s not enough for the numbers to be non-decreasing).
Output for Decreasing Sequences: For an input where there’s no increasing subsequence (for instance, a decreasing sequence like [5,4,3,2,1]), should the output be 1, assuming a single number counts as an increasing subsequence of length 1?
Output for Equal Elements: If there are multiple equal elements in the array, and these form part of the longest increasing subsequence, how should they be treated? For example, in [1,3,5,3,7], should [1,3,3,7] be considered a strictly increasing subsequence?
Multiple Subsequences of Equal Length: If there are multiple subsequences with the same longest length, should we count all of them?
Empty Array: How should an empty array be treated? Should we return 0, or consider it an exceptional case not covered by the problem?

In a typical problem-solving situation such as an interview, many of these details would be clarified in the problem statement or by the interviewer.

Problem Analysis and Key Insights

Analyzing the problem statement of LeetCode problem 673, “Number of Longest Increasing Subsequence”, provides several key insights:

Nature of Subsequence: The problem is asking about a subsequence, not a substring or subarray. In an array, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. This means that the elements in a subsequence are not required to occupy consecutive positions within the original sequence.
Strictly Increasing Requirement: The subsequences we are interested in must be strictly increasing. This means each element in the subsequence must be greater than the previous one. It’s not enough for the sequence to be non-decreasing (where subsequent elements could be equal).
Count of Longest Subsequences: The problem asks for the number of longest increasing subsequences, not just the length of the longest increasing subsequence. This means that there may be more than one longest increasing subsequence, and we need to count all of them.
Potential for Multiple Solutions: Given the constraints, it is possible that multiple longest increasing subsequences exist, which could either share elements or be completely distinct.
Constraints of the Problem: The length of the input array won’t exceed 2000, and the values in the array are within the range of -10^6 to 10^6. These constraints might affect the design of the algorithm, as it needs to handle arrays of considerable length.
Dynamic Programming Application: Given the nature of the problem (subsequences, and optimizing for the longest), it’s a hint that dynamic programming might be a suitable approach to find the solution. This is because dynamic programming is often used in optimization problems that involve making a set of choices, where each choice leads you to a new subproblem.

These insights help in understanding the problem’s requirements and in guiding the approach to a solution.

Problem Boundary

The scope of the problem “673. Number of Longest Increasing Subsequence” encompasses several aspects:

Input: The input to the problem is an array of integers, nums. The length of the array nums can be between 1 and 2000, inclusive. Each integer nums[i] in the array can range from -10^6 to 10^6.
Output: The output should be a single integer, which represents the number of longest increasing subsequences.
Functionality: The functionality required of the solution is to correctly determine the number of longest strictly increasing subsequences in the provided array.
Performance: Given the constraints of the problem (array length up to 2000), the solution should be optimized to avoid time limit exceeded errors. This implies that a brute force approach that attempts to generate all possible subsequences would not be efficient enough. We would need to leverage an approach like dynamic programming or similar optimization techniques to meet the time constraints.
Corner Cases: The solution needs to correctly handle edge cases, such as when the input array is in decreasing order, when the array has duplicate elements, or when the array has only one element. These special scenarios need to be accounted for in the implementation.
Strictly Increasing: The problem explicitly mentions that the subsequences must be strictly increasing, which means no two consecutive numbers in the subsequence can be equal.

In summary, the scope of this problem is the design and implementation of an efficient algorithm that can handle a significant range of array sizes and return the correct count of longest strictly increasing subsequences.

Establishing the boundary of the problem “673. Number of Longest Increasing Subsequence” involves understanding the limitations and constraints that the problem presents.

Input Boundary: The problem defines the input array’s size to be between 1 and 2000 elements. This establishes a boundary for the input, as well as a limit for what the algorithm must be designed to handle. Each element of the array can range from -10^6 to 10^6.
Output Boundary: The output of the problem is an integer that represents the count of the longest increasing subsequences. This integer can range from 1 (in case there is no increasing subsequence, a single number is considered as a subsequence of length 1) to the length of the input array (in case all numbers in the input array are equal, each number can be considered as a longest increasing subsequence of length 1).
Functional Boundary: The solution must be able to accurately count the number of the longest increasing subsequences, not just identify the length of such subsequences. This functionality should work for all possible cases within the defined input boundaries.
Performance Boundary: Given the constraints on the size of the input, the solution must be able to execute within reasonable time limits for the maximum input size. This means an overly complex solution with a high time complexity might not be suitable, while techniques such as dynamic programming that can reduce redundant computation would be favorable.
Exception Handling Boundary: The solution must correctly handle edge cases, such as when the input array contains a single element, all equal elements, or is in a decreasing order.

Establishing these boundaries helps ensure that your solution is robust, efficient, and able to handle all potential edge cases.

Distilling the Problem to Its Core Elements

Fundamental Concept:

The fundamental concept behind this problem is the identification of “Longest Increasing Subsequences” within a given sequence of numbers. This is a common theme in dynamic programming problems where we optimize some quantity (the length of a subsequence) over all possible choices (all possible subsequences).

Simplified Problem Description:

Suppose you have a list of numbers, and you want to find sequences of numbers within that list where each number is bigger than the one before it (we call these “increasing subsequences”). Now, you want to find the longest such sequence, but there might be more than one sequence of the same longest length. The problem is asking how many of these longest sequences there are.

Core Problem:

The core problem is counting the number of longest increasing subsequences in an array of integers.

Simplified Problem Statement:

How many of the longest strictly increasing sequences can you find in a given list of numbers?

Key Components:

Understanding what constitutes a subsequence.
Recognizing and finding increasing subsequences within the given array.
Identifying the longest of these increasing subsequences.
Counting how many of these longest subsequences exist.

Minimal Set of Operations:

Iterate over the given array of numbers.
For each number, find and update the length of the longest subsequence ending with it.
Track the number of such longest subsequences.
Continue this process for all numbers in the array.
At the end of the process, the count of the longest increasing subsequences will be available.

This minimal set of operations describes the high-level logic and not the specific implementation, which would depend on the exact approach taken (like dynamic programming).

Visual Model of the Problem

Visualizing the problem statement can be a great way to gain a deeper understanding of the problem. For problem 673, “Number of Longest Increasing Subsequence”, one effective way to visualize it is by using a sequence diagram.

Consider the example nums = [1,3,5,4,7].

We can represent the numbers in a sequence, each with a corresponding list that records the length and count of longest increasing subsequences ending at that number.

1 - [1, 1]  -> Only one subsequence ([1]) of length 1 ends here.
3 - [2, 1]  -> One subsequence ([1,3]) of length 2 ends here.
5 - [3, 1]  -> One subsequence ([1,3,5]) of length 3 ends here.
4 - [3, 1]  -> One subsequence ([1,3,4]) of length 3 ends here.
7 - [4, 2]  -> Two subsequences ([1,3,4,7] and [1,3,5,7]) of length 4 end here.

The solution to the problem is the sum of counts corresponding to the longest subsequences. In this case, it’s 2.

For any number in the sequence, visualize all strictly increasing subsequences ending at that number, update the length of the longest subsequence, and the count of such subsequences. Iterate through the sequence to build this visualization.

By visualizing the problem in this way, it’s easier to see how you might apply an algorithm to find the longest increasing subsequences and count them. This would likely involve dynamic programming, as you can build up the solution by iterating through the array and solving smaller subproblems (i.e., finding the longest subsequences ending at each number).

Problem Restatement

Let’s break down the problem “673. Number of Longest Increasing Subsequence”.

In our own words, the problem asks:

You are given a list of numbers. Your task is to figure out the maximum length of a sequence within this list where every number is strictly larger than the one before it. This is what we call an “increasing subsequence”. Now, there can be more than one such sequence of this maximum length. You have to find out how many such longest increasing subsequences exist in the given list.

For example, if the given list of numbers is [1,3,5,4,7], two longest increasing subsequences of length 4 are [1, 3, 4, 7] and [1, 3, 5, 7]. So, the answer would be 2.

Requirements and constraints:

The list will have at least 1 and at most 2000 numbers.
The numbers in the list can range from -10^6 to 10^6.
The subsequences must be strictly increasing, which means every number in the sequence must be larger than the one before it.
You need to return the count of the longest increasing subsequences, not just the length of the subsequences.

This problem involves principles of sequence analysis and optimization, and the constraints indicate that an efficient approach like dynamic programming is likely required.

Abstract Representation of the Problem

Let’s formulate an abstract representation of the problem “673. Number of Longest Increasing Subsequence”.

In abstract terms, we have a sequence S of n elements (where n can be from 1 to 2000) and each element e_i of this sequence can take a value between -10^6 and 10^6.

We need to identify all subsequences within this sequence such that for any such subsequence s_j = [e_k1, e_k2, …, e_kp], the elements follow the condition e_k1 < e_k2 < … < e_kp. Among all such subsequences, we are interested in those that have the maximum length.

Our task is to count the total number of such maximum-length subsequences. If L is the length of the longest increasing subsequence, we want to find the number of subsequences of length L.

The problem is therefore a problem of sequence analysis, where the aim is to optimize (maximize) the length of strictly increasing subsequences, and then count the number of such optimized subsequences.

The structure of this problem involves sequences and subsequences, ordering of elements, and counting, all within the constraints of the given sequence size and element range.

Terminology

This problem involves a few specialized terms and concepts, especially from the realm of computer science and more specifically, from dynamic programming and sequence analysis:

Array/Sequence: In computer science, an array or sequence is a data structure consisting of a collection of elements, each identified by at least one array index or key. In the context of this problem, the input is provided as an array of integers.
Subsequence: A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. In this problem, we are interested in finding increasing subsequences within the given array.
Strictly Increasing Subsequence: A subsequence where each element is strictly larger than the preceding one. In this problem, we have to find strictly increasing subsequences in the input array.
Longest Increasing Subsequence (LIS): In the field of sequence analysis, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. The “longest” increasing subsequence is not necessarily unique. In this problem, we need to find all the longest increasing subsequences.
Dynamic Programming (DP): Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable when the subproblems overlap, i.e., when a solution to a larger problem can be built from solutions to smaller instances of the same problem. The concept of DP is often used to solve optimization problems, like this one, as we are looking to maximize the length of the increasing subsequences.

Understanding these concepts is crucial for formulating a solution to this problem. The task requires applying dynamic programming to find all longest increasing subsequences and then count the number of such subsequences.

Problem Simplification and Explanation

Consider the input array as a road trip, where each number is a city you’re visiting and the value of the number represents the city’s elevation.

Now, you want to remember the paths of your trip where you’ve only increased in elevation - you went from a lower elevation city to a higher one, and so on (These are your increasing subsequences).

Among these paths, you are especially fond of the longest ones, where you visited the most cities in strictly increasing elevation. But you may have multiple such trips or paths that have the same maximum length.

This problem is asking for the number of these longest strictly uphill trips.

Key Concepts:

Cities (Array Elements): These represent the numbers in your array. The order in which they appear is the order in which you visit them.
Paths (Subsequences): A path is a subsequence of cities you’ve visited, not necessarily consecutive, but in the same order as they were in your trip plan.
Uphill Paths (Increasing Subsequences): These are the paths where you always move to a city of higher elevation.
Longest Uphill Paths (Longest Increasing Subsequences): Among all uphill paths, these are the ones where you’ve visited the most cities.
Number of Longest Uphill Paths: This is the final count of all the longest uphill paths you’ve had in your trip.

This problem is about carefully examining your trip (iterating through the array), recalling all the uphill paths (identifying increasing subsequences), recognizing the longest ones (finding longest increasing subsequences), and then counting how many such longest uphill trips you had (counting the number of longest increasing subsequences).

The concepts of iteration, sequence analysis, comparison, counting, and dynamic programming interplay in this problem to produce the desired output.

Constraints

Given the problem “673. Number of Longest Increasing Subsequence”, there are several characteristics that can be leveraged to formulate an efficient solution.

Input Size: The maximum size of the input array is 2000 elements. This is a moderate size that allows for solutions with quadratic time complexity.
Input Range: The numbers in the array can range from -10^6 to 10^6. While the large range doesn’t offer an immediate benefit for optimization, it implies we cannot apply counting sort or similar algorithms.
Ordering Matters: Because we are looking for strictly increasing subsequences, the order of elements in the array is significant. We can exploit this by iterating over the array and building our solution progressively.
Subsequence Counting: Instead of just identifying the longest increasing subsequence, we’re also interested in the count of such subsequences. This makes the problem a good candidate for a dynamic programming approach, where we keep track of both length and count of longest subsequences at each element.
Increasing Nature: The problem specifically asks for increasing subsequences. This implies that a larger number can only extend a subsequence ended by a smaller number. It guides us to use a bottom-up approach: iterate the array from left to right, and for each element, consider all elements on its left side only.
Longest Subsequences: Because we’re interested in the longest increasing subsequences, we can ignore any subsequences that are shorter than the longest we’ve found so far. This allows us to prune our search space and avoid unnecessary computation.

Looking at these characteristics and constraints, it seems like a dynamic programming solution, where for each element in the array we maintain information about the longest increasing subsequence ending at that element, would be a promising approach to efficiently solve the problem.

The constraints of the problem can often offer important insights that can guide our approach to solving it. In this problem, the constraints are as follows:

The length of the given array is between 1 and 2000.
The numbers in the array are integers and can range from -10^6 to 10^6.

Key insights from these constraints are:

Problem Scope: The maximum length of the input array is 2000. This suggests that the problem could potentially be solved using an algorithm with a time complexity of O(n^2) or even O(n log n), both of which are reasonable for this problem size. This is a hint that a dynamic programming approach, which often has such time complexities, could be a feasible solution.
Data Type and Range: The array contains integers which can range from -10^6 to 10^6. This large range of integer values indicates that approaches like counting sort are likely not feasible due to memory limitations. However, this range also suggests that there will be ample opportunity for strictly increasing subsequences to exist within the input array.
Increasing Subsequences: The requirement for subsequences to be strictly increasing implies that larger numbers can only extend a subsequence if they are larger than the last number in the subsequence. This observation should guide our approach to solve the problem.

Overall, these constraints suggest a dynamic programming approach where we iterate over the array, maintaining at each step the best solution (longest increasing subsequences) found so far, and using this information to construct the best solution for the next step.

Case Analysis

Let’s go through a range of examples to explore different aspects of this problem:

1. Case of Single Element (“SingleTown”):

Input: nums = [5]
Output: 1
Explanation: Here, the array has only one element, which itself forms a longest increasing subsequence. So, the answer is 1.

2. Case of Increasing Elements (“UpHillJourney”):

Input: nums = [1, 2, 3, 4, 5]
Output: 1
Explanation: The entire array itself is a longest increasing subsequence. There's only one such subsequence in this case.

3. Case of Decreasing Elements (“DownHillJourney”):

Input: nums = [5, 4, 3, 2, 1]
Output: 5
Explanation: Since the elements are strictly decreasing, the longest increasing subsequence will only have one element. There are 5 such subsequences, one for each element in the array.

4. Case of Identical Elements (“FlatLands”):

Input: nums = [2, 2, 2, 2, 2]
Output: 5
Explanation: Here, all the elements are the same. So, again the longest increasing subsequence is of length 1 and there are 5 such subsequences, one for each element.

5. Case of Non-Consecutive Increasing Subsequences (“IntermittentRise”):

Input: nums = [1, 3, 2, 4, 5, 3, 7, 8]
Output: 3
Explanation: The longest increasing subsequences here are [1, 2, 4, 5, 7, 8], [1, 3, 4, 5, 7, 8], and [1, 3, 4, 5, 7, 8] (by starting from the second occurrence of 3). So, the output is 3.

6. Case of Maximum Input Size (“BigCity”):

Input: nums = [1, 2, 3, ..., 2000] (2000 elements in total)
Output: 1
Explanation: For a case like this, we're mostly testing the performance of our solution. The entire array forms a single longest increasing subsequence.

The first four cases cover the edge cases, where the array has only one element, all elements are identical, or elements are strictly increasing or decreasing. The fifth case explores the scenario where multiple longest increasing subsequences exist, and the last one tests the efficiency of the solution when dealing with the largest input size.

Visualizing these cases can help in understanding the problem and identifying patterns. Here’s how you could visualize the given cases:

Case of Single Element (“SingleTown”):
The sequence is represented as: [5]
Here, only one city is present. So, only one trip is possible, which is to the city itself.
Case of Increasing Elements (“UpHillJourney”):
The sequence is represented as: [1 → 2 → 3 → 4 → 5]
This represents a single uphill journey, continuously going from one city to the next one with increasing elevation.
Case of Decreasing Elements (“DownHillJourney”):
The sequence is represented as: [5, 4, 3, 2, 1]
Here, every city has a lower elevation than the previous one. So, each city itself forms an increasing subsequence of length 1.
Case of Identical Elements (“FlatLands”):
The sequence is represented as: [2, 2, 2, 2, 2]
In this case, all cities are at the same elevation. Each city itself forms an increasing subsequence of length 1.
Case of Non-Consecutive Increasing Subsequences (“IntermittentRise”):
The sequence is represented as: [1 → 3, 2 → 4 → 5, 3 → 7 → 8]
In this case, there are several increasing subsequences, some of which overlap, forming the longest increasing subsequences.
Case of Maximum Input Size (“BigCity”):
The sequence is represented as: [1 → 2 → 3 → … → 2000]
This is simply a longer version of the “UpHillJourney” case, testing the algorithm’s efficiency with large inputs.

These visual representations help illustrate the structure of the different sequences and how the longest increasing subsequences are formed within each.

Analyzing different cases can reveal a number of insights about the problem. Here are some key insights:

Single Element Array: If the input array has only a single element, then that element itself forms the longest increasing subsequence.
Increasing Elements: If the elements of the array are strictly increasing, the longest increasing subsequence is the array itself. There can’t be more than one longest increasing subsequence in such case.
Decreasing Elements: If the elements of the array are strictly decreasing, every element forms a longest increasing subsequence, as the length of each increasing subsequence can only be 1.
Identical Elements: If all the elements in the array are the same, then again, each element forms a longest increasing subsequence.
Non-Consecutive Increasing Subsequences: In case there are multiple non-consecutive increasing subsequences of the same length, all of them should be considered.
Large Input Size: The solution needs to be efficient to handle the maximum input size within reasonable time. This suggests that an algorithm with time complexity of O(n^2) or O(n log n) would likely be necessary, hinting towards dynamic programming or binary search based solutions.

These insights can guide the approach towards formulating an algorithm to solve the problem efficiently.

Identification of Applicable Theoretical Concepts

The “673. Number of Longest Increasing Subsequence” problem can benefit from several fundamental mathematical and computer science concepts. Specifically, Dynamic Programming (DP) and the concept of subsequence are critical here.

Dynamic Programming: DP is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. It is ideal for optimization problems such as this one, where we need to find the number of longest increasing subsequences.
In this problem, we could use a DP approach to store the length of the longest subsequence that ends at each index and the count of these longest subsequences. As we iterate through the array, for each element, we would update these values based on the previously computed results, making this problem a perfect candidate for DP.
Subsequence concept: A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. In this problem, understanding how to identify a subsequence (especially an increasing subsequence) and the relationships between subsequences in an array is important.
Array manipulation: As with many problems that involve arrays, being proficient in common operations like traversing the elements, comparing element values, and maintaining and updating a record of computations (like longest subsequence length and count in this case) is crucial to efficiently solving this problem.

There are no direct mathematical theories or metrics applicable to simplify this problem. However, an understanding of the above-mentioned concepts would significantly help to develop an efficient solution.

Simple Explanation

Imagine you are on a road trip and you want to visit a series of towns. Now, each of these towns is located at different altitudes. You have a special rule for your road trip - you must always travel to a town that is at a higher altitude than your current town.

Now, you want to make your road trip as long as possible, visiting the maximum number of towns, following your rule. You also want to know how many such different road trips you can plan.

In this scenario, each town represents a number in our list, and the altitude of the town is the value of the number. A road trip is an increasing subsequence, where each next town (number) you visit is higher (greater) than the previous one.

The longest road trip you can make is the longest increasing subsequence. And since there may be multiple different ways to plan such longest road trips, the number of such different road trips is what we are asked to find in this problem.

Therefore, in the context of this problem, you are given a list of numbers (the towns and their altitudes), and you need to figure out the maximum number of towns you can visit on your longest road trip (the longest increasing subsequence), and how many such different longest road trips you can plan (the count of longest increasing subsequences).

Problem Breakdown and Solution Methodology

Let’s break down the approach to solve this problem using our road trip metaphor:

Initialization:
At the start of our journey, we’re at our home town and haven’t visited any other towns yet. So, we initialize two lists or arrays, lengths and counts, both of the same size as our input array, nums (the towns we can visit). In lengths, each element represents the length of the longest road trip ending at each town. And in counts, each element stores the number of such longest road trips ending at each town. Initially, each town can be a road trip on its own, so we fill both lists with 1s.
Building road trips:
We start from our home town (the first town in nums) and try to extend our road trip to each town that is at a higher altitude (greater value). For each town j, we look back at all previous towns i (where i < j), and if nums[i] is less than nums[j], that means we can go on a road trip from town i to town j.
Here, two cases arise:
- If the road trip from town i to town j is longer than any road trip we’ve previously ended at town j (i.e., lengths[i] + 1 > lengths[j]), then we’ve found a longer road trip ending at town j. So, we update lengths[j] to lengths[i] + 1. Also, the number of longest road trips ending at town j is now the same as the number of longest road trips ending at town i, so we set counts[j] to counts[i].
- If the road trip from town i to town j is of the same length as the longest road trips we’ve previously ended at town j (i.e., lengths[i] + 1 equals lengths[j]), that means we’ve found a different way to have a longest road trip ending at town j. So, we add the number of longest road trips ending at town i to counts[j].
Finding longest road trips:
After checking all towns, we find out the length of the longest road trip by looking for the maximum value in lengths.
Counting longest road trips:
Finally, to get the number of such longest road trips, we count all road trips that have the same length as our longest road trip. We do this by going through counts and summing up the counts corresponding to the longest road trips.

Now, let’s walk through an example.

Consider nums = [1,3,5,4,7].

Initialize lengths = [1,1,1,1,1] and counts = [1,1,1,1,1].
For j = 1 (nums[j] = 3), we find nums[0] < nums[1], so we can go on a road trip from town 0 to town 1. We update lengths[1] to lengths[0] + 1 = 2 and counts[1] to counts[0] = 1.
For j = 2 (nums[j] = 5), we find nums[0] < nums[2] and nums[1] < nums[2], so we can go on a road trip from towns 0 and 1 to town 2. As the road trips from both towns are longer than any road trip we’ve previously ended at town 2, we update lengths[2] to lengths[1] + 1 = 3 and counts[2] to counts[1] = 1.
Similarly, we continue the process for the remaining towns, updating lengths and counts as necessary.
Finally, we find the length of the longest road trip is 4 (max value in lengths), and the number of such longest road trips is 2 (sum of counts where lengths is 4).

Changes in the problem’s parameters would affect the solution in the following ways:

Increasing the size of nums would increase the computational complexity of the solution. This is because for each element, we look back at all previous elements, leading to a time complexity of O(n^2).
If the elements in nums are not distinct, that would increase the number of longest increasing subsequences, as each identical element can start a new increasing subsequence of the same length.
If the elements in nums are in strictly increasing or strictly decreasing order, that would decrease the number of longest increasing subsequences to 1 and nums.length, respectively.

Inference of Problem-Solving Approach from the Problem Statement

Let’s break down the key terms and concepts:

Integer Array (nums): The problem provides an integer array, nums, which is a fundamental data structure. Knowing that we’re working with an array suggests we might use indexing, iterating, or other array manipulation methods. Also, arrays often lend themselves to dynamic programming solutions, which is the case here.
Longest Increasing Subsequence: This is a common problem in computer science and often solved with dynamic programming. The term “increasing” tells us we’re looking for sequences where each number is greater than the previous one, and “longest” tells us we’re trying to maximize something.
Number of Sequences: Not only do we want the longest increasing subsequences, but we also want to know how many of such sequences exist. This suggests that our solution needs to keep track of counts in addition to lengths, which hints at the use of multiple arrays or an array of pairs (or a similar data structure).
Strictly Increasing: This term clarifies that the numbers in each sequence must increase (not stay the same). It tells us that when we’re looking to extend a subsequence, we need to ensure the next number is greater than the last number in the current subsequence.

These terms and concepts suggest a dynamic programming solution, where we iterate over the array and for each number, look back at all previous numbers to see if we can extend any increasing subsequences. This approach lets us build up the solution incrementally, using previously computed results to solve the current step, which is characteristic of dynamic programming.

A useful way to recognize the properties of the problem would be to use a table, where each row represents an element in the input array, and each column represents either the length of the longest increasing subsequence ending at the corresponding element (let’s call this lengths) or the number of longest increasing subsequences ending at the corresponding element (let’s call this counts).

Let’s visualize this with the example nums = [1,3,5,4,7]. Here’s how you might fill out the table:

Initialize lengths and counts arrays with size equal to the length of nums, filled with 1s. This represents that each element is a valid subsequence of length 1.
For each element, compare it with all previous elements.
- If nums[i] > nums[j], then we’ve found an increasing subsequence. Now we have two cases:
  - If lengths[j] + 1 > lengths[i], this means we’ve found a longer subsequence ending at i, so we update lengths[i] and make counts[i] equal to counts[j].
  - If lengths[j] + 1 == lengths[i], this means we’ve found a new subsequence of the same length as the longest found so far, so we add counts[j] to counts[i].

The table would look like this:

nums:    1 3 5 4 7
lengths: 1 2 3 3 4
counts:  1 1 1 1 2

Here, lengths[i] represents the length of the longest increasing subsequence ending at nums[i], and counts[i] represents the number of such subsequences. This table shows that there are two longest increasing subsequences: [1, 3, 4, 7] and [1, 3, 5, 7].

This visualization helps to see how dynamic programming is being applied. By using previously calculated lengths and counts, you can build up the solution to the entire problem.

Dynamic Programming (DP) is a method for solving optimization problems by breaking them down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

Here are the clues in the problem statement that suggest a Dynamic Programming solution:

Optimization problem: The problem is asking for the “longest” increasing subsequence, indicating that it is an optimization problem. DP is often used for optimization problems.
Overlapping subproblems: The longest increasing subsequence ending at each position i depends on the longest increasing subsequences ending at all previous positions. This hints at overlapping subproblems, which is a characteristic of DP problems.
Dependence on previous computations: In the problem, we need to look at all previous elements in the array to determine the solution at a given index. This dependence on previous computations is typical of DP problems.
Subsequence problem: Problems involving subsequences often have a DP solution, because they involve making decisions at each position (to include or not to include a certain element, for example), and those decisions can be made based on the results of previous decisions.

For these reasons, the problem hints at a DP solution. In this specific problem, we use DP to keep track of the longest increasing subsequences ending at each position and their counts, and we build up these arrays incrementally by making decisions based on previous entries.

Simple Explanation of the Proof

Here’s a high-level breakdown of why the algorithm works:

At the heart of this problem, we’re dealing with subsequences in an array. A subsequence is just a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

In this particular problem, we’re dealing with increasing subsequences, which means each element in the subsequence is larger than the previous one. And we’re not just looking for any increasing subsequences, we’re looking for the longest ones.

Now, when we go through our array, for each number, we check all the numbers that came before it. If the current number is greater than one of those previous numbers, that means we can form an increasing subsequence.

Here’s the important part: If we’ve already found an increasing subsequence ending at that previous number, then we can just extend that subsequence by adding our current number to the end. That’s why we keep track of the longest increasing subsequence ending at each number: so we can extend it if we find a bigger number.

But there’s one more thing we need to keep track of: the number of these longest subsequences. Why? Because it’s possible to have more than one longest increasing subsequence. For example, if our array is [1,2,3,4], then [1,2,3] and [1,2,4] are both longest increasing subsequences. So whenever we find a new longest subsequence, we need to update our count.

Now, as for proof that this algorithm works, consider this: the longest increasing subsequence ending at any position in the array must include each smaller number before it in the array (if any exist). Therefore, by extending the longest increasing subsequences we’ve found so far, we are guaranteed to find all the longest increasing subsequences in the array.

In other words, by the time we reach the end of the array, we’ve considered every possible longest increasing subsequence, which means our counts are correct. Therefore, the algorithm is correct.

Let’s break down the problem into more granular, actionable steps:

Initialize two arrays: lengths and counts. Both arrays have the same size as the input array. lengths[i] will hold the length of the longest increasing subsequence ending at index i, while counts[i] will hold the number of such longest increasing subsequences. Initialize all entries of lengths to 1 (since a single number itself can be considered a subsequence of length 1) and all entries of counts to 1 (we start with one way to form a subsequence - with the number itself).
Start iterating over the input array: For each index i, we will compare the current number with all the previous numbers in the array from indices 0 to i - 1.
Inside this iteration, for each index j from 0 to i - 1, check if the number at the current index i is greater than the number at index j. If it is, we have two scenarios:
a. If the length of the longest subsequence ending at j plus one (lengths[j] + 1) is greater than the length of the longest subsequence we have so far at i (lengths[i]), it means we have found a new longest subsequence by including the number at i in the subsequence ending at j. In this case, we update lengths[i] to lengths[j] + 1, and set counts[i] equal to counts[j] (since all ways of forming the longest subsequence at j can be extended to i).
b. If the length of the longest subsequence ending at j plus one (lengths[j] + 1) is equal to the length of the longest subsequence we have so far at i (lengths[i]), it means we have found an alternative way to form the longest subsequence at i. In this case, we add counts[j] to counts[i] (since all ways of forming the longest subsequence at j provide new ways to form the longest subsequence at i).
Continue iterating: Once we’ve iterated through the entire array, we know the length of the longest increasing subsequence (the maximum value in lengths) and we can use this to find the number of such subsequences (the sum of counts[i] for all i where lengths[i] is equal to the maximum length).
Return the count: The number of longest increasing subsequences is our answer.

Independently solvable parts: Each step in the iterations can be performed independently, since they all operate on different indices of the array. However, the result depends on the cumulative information gathered, so the problem as a whole can’t be easily broken down into completely independent parts.

Repeatable patterns: The most repeatable pattern in this solution is the comparison of the current number with all previous numbers in the array. This comparison, along with the potential updates to lengths and counts, is performed for each number in the array, representing a clear repeatable pattern.

Solution Approach and Analysis

To solve this problem, we are essentially performing an “expedition” through the “mountain range” of numbers provided in the array, where each number is a “peak”. Our goal is to find the longest path of strictly ascending peaks and determine how many such paths exist.

We’ll use Dynamic Programming, which can be thought of as breaking a larger problem into smaller subproblems, then combining their solutions to get the final solution.

Here’s a step-by-step breakdown:

Setting Up Base Camps: Initialize two arrays, lengths and counts of the same size as the input array. lengths[i] will represent the length of the longest path up to and including peak i, while counts[i] will represent how many such paths exist. Every peak is a path of length 1 on its own, so initially set every element in both arrays to 1.
Begin the Expedition: Start iterating over the array. For each index i, we’ll check all previous peaks (indices j where 0 <= j < i) to see if we can extend any paths ending at j to i.
Extending the Paths: If nums[i] is greater than nums[j] (meaning we can “ascend” from peak j to i), we’ll look at lengths[j] + 1 (the length of the path through j extended to i). Two situations can occur:
a. If lengths[j] + 1 is greater than lengths[i], it means we’ve found a new longest path ending at i by extending the path from j. So, we update lengths[i] to lengths[j] + 1, and set counts[i] to counts[j] since the new longest paths are the extensions of the paths ending at j.
b. If lengths[j] + 1 equals lengths[i], it means we’ve found another path of the same longest length ending at i. So, we add counts[j] to counts[i] because all the paths ending at j provide additional paths ending at i.
Finding All Longest Paths: After we’ve finished our expedition through all the peaks, we can find the longest path length (the maximum value in lengths). Then, we sum up the counts of all paths of that length (add counts[i] for every i where lengths[i] is equal to the maximum length).
The Result: The total number of longest paths is our answer.

Let’s consider an example:

nums = [1, 3, 5, 4, 7]

lengths = [1, 2, 3, 3, 4] (lengths of longest paths ending at each index)
counts = [1, 1, 1, 1, 2] (counts of longest paths ending at each index)

The longest path length is 4 and there are 2 paths of that length, so our answer is 2.

Change in Problem Parameters: If the input array becomes larger, it would take more time to compute the solution as the algorithm needs to iterate through each pair of elements. If the numbers in the array are not unique or not in a strictly increasing or decreasing order, then it will affect the counts of longest increasing subsequences.

By understanding the above steps and the example, you’ll have a better grasp on how to approach similar problems. The critical part is understanding how to extend the subproblems (the paths ending at each peak) in a way that maintains the necessary information (both the lengths and counts).

Identify Invariant

In the context of this problem, the invariant can be seen as the following statement:

“At each index i, the lengths[i] correctly stores the length of the longest increasing subsequence ending at i, and counts[i] correctly stores the number of such sequences.”

This is an invariant because it holds true throughout the execution of the algorithm. At each step, we ensure it holds by correctly updating the lengths and counts arrays based on the previous indices. The lengths array always holds the length of the longest increasing subsequences up to the current index, and the counts array always holds the number of such subsequences. This invariant is crucial for our dynamic programming solution to correctly calculate the final result.

Identify Loop Invariant

In the context of this problem, the loop invariant is as follows:

“For each i in the outer loop, and each j in the inner loop (where j < i), lengths[i] and counts[i] correctly represent the length of the longest increasing subsequence ending at index i and the count of such subsequences, respectively, considering all indices from 0 to j.”

In simpler terms, for every pair of indices i and j that the loops visit, the lengths and counts arrays will accurately reflect the maximum length and number of strictly increasing subsequences that end at index i, considering only elements from the beginning of the array to index j.

This is our loop invariant and it holds true before the loop starts (as initially, all lengths and counts are 1), during each iteration (as we correctly update lengths and counts for each i and j), and after the loop finishes (when lengths and counts represent the lengths and counts for all strictly increasing subsequences in the entire array).

Establishing this loop invariant helps us reason about the correctness of our dynamic programming solution.

In the context of this problem, the overall invariant and the loop invariant essentially represent the same condition - that at any point in the execution of the algorithm, for each index i, lengths[i] correctly represents the length of the longest increasing subsequence ending at i, and counts[i] correctly represents the number of such subsequences.

However, they are used in slightly different ways:

The term “invariant” is often used to describe a condition that holds true throughout the execution of an algorithm. It’s a broader concept that applies to the algorithm as a whole.
The term “loop invariant”, on the other hand, is specifically associated with loops in an algorithm. It describes a condition that holds true before, during, and after each iteration of a loop.

So while the condition they represent is the same in this case, the terms “invariant” and “loop invariant” are used in different contexts to help reason about the correctness and behavior of different parts of the algorithm.

Invariant seems to be using one variable whereas the loop invariant is using two variables. Is that right?

Not necessarily. Both invariants and loop invariants can involve any number of variables. The number of variables depends on the specific property or condition you’re expressing, not on whether it’s an invariant or a loop invariant.

In this specific problem:

The overall invariant states that “At each index i, lengths[i] correctly stores the length of the longest increasing subsequence ending at i, and counts[i] correctly stores the number of such sequences.”
The loop invariant states that “For each i in the outer loop, and each j in the inner loop (where j < i), lengths[i] and counts[i] correctly represent the length of the longest increasing subsequence ending at index i and the count of such subsequences, respectively, considering all indices from 0 to j.”

In both cases, we are essentially talking about the correctness of the lengths and counts arrays at different stages of the algorithm. While the loop invariant does involve two indices (i and j) because we’re dealing with a nested loop, both invariants are essentially about the same two variables (lengths[i] and counts[i]). So it’s not accurate to say that invariants involve one variable while loop invariants involve two variables. The number of variables depends on the specific condition or property we’re expressing.

Thought Process

Here’s a detailed step-by-step breakdown:

Problem Understanding: The problem asks for the count of the longest increasing subsequences in an array. So, not only do we need to find the length of the longest increasing subsequence (like in LeetCode 300), but also count how many such longest subsequences exist.
Key Insights: A subsequence is not the same as a subarray - elements in a subsequence don’t have to be contiguous. Also, the subsequence needs to be strictly increasing, meaning each element must be greater than the one before. These constraints suggest that a brute force approach (generating all subsequences) would not be efficient due to the large input size constraint.
Approach: The problem is a classic Dynamic Programming (DP) problem, similar to the Longest Increasing Subsequence problem but with an added layer of complexity. DP is suitable here because we can break the problem down into overlapping subproblems - the longest increasing subsequence ending at each index.
State Transition: For each index, we’ll calculate the length of the longest subsequence ending there, and also keep count of the number of such subsequences. We compare each index with all indices before it - if nums[i] > nums[j], we’ve found a longer increasing subsequence, and we update the lengths and counts accordingly.
Initialization: We’ll create two arrays, lengths and counts, of the same size as nums, and initialize them to 1. This is because a single number is an increasing subsequence of length 1.
Result: We need the count of the longest increasing subsequences, so we’ll find the maximum length, and then sum the counts of all subsequences with that length.

Here’s how the solution can be implemented in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0

        n = len(nums)
        lengths = [1] * n  # lengths[i] = length of longest ending in nums[i]
        counts = [1] * n  # count[i] = number of longest ending in nums[i]

        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if lengths[j] >= lengths[i]:
                        lengths[i] = lengths[j] + 1
                        counts[i] = counts[j]
                    elif lengths[j] + 1 == lengths[i]:
                        counts[i] += counts[j]

        longest = max(lengths)
        return sum(c for l, c in zip(lengths, counts) if l == longest)				

This function will return the number of longest increasing subsequences in the input list.

Establishing Preconditions and Postconditions

Parameters:
- The method findNumberOfLIS(nums) takes a single input parameter, nums.
- This parameter is of type List[int], which represents a list of integers.
- The parameter nums represents the integer array mentioned in the problem statement.
Preconditions:
- Before the method is called, it is assumed that nums is a list of integers, not empty, and has a length between 1 and 2000 (both inclusive) as per the problem constraints. Each element in nums is an integer between -10^6 and 10^6.
- The input list nums is not required to be in any specific state or order.
Method Functionality:
- This method is expected to return the number of longest increasing subsequences in the given integer array.
- It iterates over the nums array and calculates the longest increasing subsequence ending at each index using dynamic programming.
Postconditions:
- After the method has been called and has returned, the original input array nums remains unmodified.
- The return value represents the number of longest increasing subsequences within the input array nums.
- The method has no side effects as it does not modify any global state or the input array.
Error Handling:
- The method does not explicitly handle errors or exceptions. If the input does not meet the preconditions (for example, if nums is not a list of integers or is empty), the method could raise a type error, value error or other unhandled exceptions.
- It is expected that the function’s preconditions are met prior to calling, and it’s the caller’s responsibility to ensure this.

Problem Decomposition

Problem Understanding:
- The problem is to find all the longest increasing subsequences in a given array. The subsequence needs to be strictly increasing. The key components are the array itself and the concept of “increasing subsequence”.
Initial Breakdown:
- We can break down the problem into two major parts:
  - Finding the length of the longest increasing subsequence (LIS).
  - Counting the number of such longest increasing subsequences.
Subproblem Refinement:
- The first subproblem can be further broken down into:
  - Iterating over the array.
  - For each element, finding the maximum length of the increasing subsequences ending at it.
- The second subproblem involves:
  - Keeping track of the count of increasing subsequences of each length as we determine the LIS.
  - Once we know the length of the LIS, returning the count corresponding to that length.
Task Identification:
- A repeated task in this problem is iterating over the array, and for each element, checking previous elements to determine if they form an increasing subsequence with the current element.
Task Abstraction:
- The abstract task here is “for each element in the array, determine the longest increasing subsequence ending at that element, and count the number of such subsequences”.
Method Naming:
- A descriptive name for this task could be findNumberOfLIS(nums).
Subproblem Interactions:
- The tasks need to be performed in the order described: first, we determine the LIS, then we count the number of such subsequences.
- The second task depends on the first task as we need to know the length of the LIS to count the number of such subsequences.

From Brute Force to Optimal Solution

A brute force solution would involve generating all possible subsequences of the given array and checking which of these are increasing subsequences. For each increasing subsequence, we would keep track of its length and the count of subsequences of each length. Finally, we would return the count corresponding to the maximum length.

Here is a rough Python pseudocode:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def bruteForce(nums):
    subsequences = getAllSubsequences(nums)
    max_length = 0
    counts = {}
    for subseq in subsequences:
        if isIncreasing(subseq):
            length = len(subseq)
            max_length = max(max_length, length)
            counts[length] = counts.get(length, 0) + 1
    return counts[max_length]

Inefficiencies:

Time Complexity: Generating all subsequences is a power set problem, which has a time complexity of O(2^n), where n is the number of elements in the array. This is extremely inefficient for larger inputs.
Space Complexity: We need to store all subsequences which also requires O(2^n) space.

Optimization process:

Step 1:

Identify overlapping subproblems: The brute force solution repeatedly checks similar or overlapping subsequences. We can avoid this redundancy by solving each subproblem only once and storing its result. This suggests using Dynamic Programming.

Step 2:

Formulate a Dynamic Programming solution: Instead of checking all subsequences, we can iterate over the array from left to right. For each element, we can use previously computed results to determine the length of the longest increasing subsequence ending at that element and the count of such subsequences.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def findNumberOfLIS(nums):
    if not nums: return 0
    n = len(nums)
    lengths = [1] * n  # lengths[i] = length of longest ending at nums[i]
    counts = [1] * n  # count[i] = number of longest ending at nums[i]
    for i, num in enumerate(nums):
        for j in range(i):
            if nums[j] < num:
                if lengths[j] >= lengths[i]:
                    lengths[i] = lengths[j] + 1
                    counts[i] = counts[j]
                elif lengths[j] + 1 == lengths[i]:
                    counts[i] += counts[j]
    longest = max(lengths)
    return sum(c for l, c in zip(lengths, counts) if l == longest)

In this optimized solution, we maintain two arrays: ’lengths’ to store the length of the longest increasing subsequence ending at each position, and ‘counts’ to store the count of longest increasing subsequences ending at each position.

Time Complexity: The time complexity is now O(n^2), where n is the number of elements in the array. This is because we have two nested loops iterating over the array.

Space Complexity: The space complexity is O(n), required for the ’lengths’ and ‘counts’ arrays. This is a significant improvement from the brute force solution.

The brute force solution results in Memory Limit Exceeded.

Here is the Python code for the brute force solution. Note that this solution generates all possible subsequences, so it will have a time complexity of O(2^n) and may not perform well for larger inputs.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from typing import List

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # Generate all subsequences
        subsequences = self.getSubsequences(nums)

        # Find the longest increasing subsequences
        max_length = 0
        counts = {}
        for subseq in subsequences:
            if self.isIncreasing(subseq):
                length = len(subseq)
                max_length = max(max_length, length)
                counts[length] = counts.get(length, 0) + 1

        return counts[max_length]

    # Generate all subsequences
    def getSubsequences(self, nums: List[int]) -> List[List[int]]:
        subsequences = [[]]
        for num in nums:
            subsequences += [sub + [num] for sub in subsequences]
        return subsequences

    # Check if a sequence is increasing
    def isIncreasing(self, nums: List[int]) -> bool:
        return all(nums[i] < nums[i+1] for i in range(len(nums) - 1))

In this solution, the getSubsequences method generates all possible subsequences by starting with an empty subsequence and successively adding each number in the original array to all previously generated subsequences. The isIncreasing method checks whether a given subsequence is strictly increasing by comparing each number to the next one. In the main findNumberOfLIS method, we iterate through all generated subsequences, keep track of the length and count of the longest increasing subsequences, and finally return the count of the longest ones.

Code Explanation and Design Decisions

Let’s go over the Python code provided for the brute force solution and discuss the points you mentioned.

Initial Parameters: The only initial parameter to the findNumberOfLIS method is nums, which is a list of integers. This list represents the sequence of numbers for which we are trying to find the number of longest increasing subsequences.
Primary Loop: The primary loop in the getSubsequences method iterates over each number in the input list nums. Each iteration of this loop represents the generation of all possible subsequences that include the current number.
Conditions/Branches: There are no explicit conditions or branches within the main loop. However, the list comprehension inside the loop implicitly includes a branching condition: for each existing subsequence, it either includes the current number (creating a new subsequence) or does not.
Updates/Modifications: The list of subsequences is updated in each iteration by adding new subsequences that include the current number. This modification is necessary to generate all possible subsequences, which we need to check to find the longest increasing ones.
Invariant: A crucial invariant in the code is the fact that after each iteration in getSubsequences, the subsequences list includes all subsequences of the processed part of the input list. This invariant is essential to ensure that we consider all possible subsequences when looking for the longest increasing ones.
Final Output: The final output of the findNumberOfLIS method is the number of longest increasing subsequences in the input list. This output is the direct answer to the problem statement, satisfying its requirements by determining not just the length of the longest increasing subsequences, but also the number of such subsequences.

This explanation aims to clarify the conceptual logic behind the code, rather than the syntax or Python-specific features. Understanding these aspects should help in comprehending the problem-solving approach used here, as well as applying similar logic to other problems.

Coding Constructs

Let’s analyze the brute force solution code to understand its high-level strategies and logical elements.

High-Level Strategies: This code uses brute force generation of subsequences combined with the concept of dynamic programming to solve the problem. It first generates all possible subsequences, then checks each one to see if it’s increasing and keeps track of the longest such subsequences.
Purpose of the Code to a Non-programmer: If I were to explain this code to a non-programmer, I’d say it’s like going through a list of numbers and trying to find all possible paths of increasing numbers, just like walking through a hilly terrain and counting all the different ways you can walk uphill from the start to the highest point.
Logical Elements: This code utilizes iteration (looping over a list of numbers), recursion (calling the same function within its definition to generate subsequences), conditionals (checking if a subsequence is increasing), and comparison operations (comparing lengths of subsequences to find the longest).
Algorithmic Approach in Plain English: The code starts by looking at all the possible subsets of numbers from our original list (even if it has to repeat this task many times). For each of these subsets, it checks if the numbers are in ascending order. If they are, it compares the length of this ascending subset with the longest one it has found so far. If it’s longer, it updates its record of the longest length and how many times it has seen subsequences of this length. If it’s the same length as the longest it has seen before, it just updates how many times it has seen subsequences of this length.
Key Steps or Operations: The key steps this code performs are the generation of subsequences, checking if a subsequence is increasing, and updating the record of the longest increasing subsequences. These operations are necessary to exhaustively search through all possibilities and find the longest increasing subsequences, which is the core requirement of the problem.
Algorithmic Patterns or Strategies: The code uses the exhaustive search pattern to generate all subsequences and then apply a condition (increasing order) on each of them. It also uses a form of dynamic programming by storing and updating the maximum length found so far and its count, thus utilizing past computation results to avoid redundant work.

Language Agnostic Coding Drills

Concept Identification:
Here are the main language-agnostic concepts used in this code:
a. Iteration: It involves looping over a sequence of data.
b. Recursion: The process of solving a problem where the solution depends on solutions to smaller instances of the same problem.
c. Conditional Branching: It involves making a decision in the code about which statement to execute based on a condition.
d. Data Storage and Retrieval: It’s about storing data in a structured manner and retrieving it when required.
e. Comparison Operations: It involves comparing data according to certain criteria.
Difficulty Classification:
Here they are listed from easiest to hardest:
a. Comparison Operations (Easy): This is a fundamental concept in all programming languages, used to compare values.
b. Conditional Branching (Easy): Almost all code uses conditions to control the flow of execution, so it’s a fundamental concept but requires a bit more reasoning than simple comparisons.
c. Iteration (Intermediate): Iteration is a step up in complexity, as it involves not only comparing items and controlling execution flow but also tracking progress through a sequence.
d. Data Storage and Retrieval (Intermediate): Storing data and retrieving it effectively is a critical aspect of many programs. It requires a good understanding of data structures.
e. Recursion (Hard): Recursion is typically one of the more challenging concepts for beginners. It requires thinking in terms of problem decomposition and often involves more complex control flow than iterative solutions.
Problem-Solving Approach:
Here’s how you could use these concepts to solve this problem:
a. Iteration: Start by iterating through the list of numbers. This loop will form the basis of our solution, with each iteration representing a possible start of a new subsequence.
b. Recursion: For each number in the list, start a new “branch” of computation, checking all possible subsequences that start with this number. This is done by recursively calling our function with a smaller version of our list.
c. Conditional Branching: Within our recursion, we’ll need to make decisions based on our current state. If our current number is greater than the previous number in our subsequence, we have a valid “increasing” step and we can continue our recursion with this branch.
d. Data Storage and Retrieval: We need to store the longest length found so far and the number of sequences of that length. This requires an effective way to store this data and retrieve it when needed.
e. Comparison Operations: Finally, with our stored data, we need to compare each newly found subsequence’s length with our stored longest length. If it’s longer, we update our stored length and reset the count. If it’s equal, we increment our count.

Targeted Drills in Python

Let’s break down the solution into smaller coding drills.

Comparison Operations:

This is a simple comparison between two integers in Python.

1
2
3
4
5
6
7
a = 5
b = 10

if a < b:
    print("a is less than b")
else:
    print("a is not less than b")

Conditional Branching:

This is a simple Python code demonstrating the use of conditional statements.

1
2
3
4
5
6
7
8
a = 10

if a > 0:
    print("a is positive")
elif a < 0:
    print("a is negative")
else:
    print("a is zero")

Iteration:

Here we are iterating over a list of integers in Python.

1
2
3
4
numbers = [1, 2, 3, 4, 5]

for number in numbers:
    print(number)

Data Storage and Retrieval:

This is an example of storing and retrieving data from a Python list.

1
2
3
4
5
6
7
numbers = [1, 2, 3, 4, 5]

# Store data
numbers.append(6)

# Retrieve data
print(numbers[2])  # It will print 3

Recursion:

This is a simple example of a recursive function in Python. It calculates the factorial of a number.

1
2
3
4
5
6
7
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # It will print 120

After practicing these basic drills, we can proceed to the problem-specific drills.

Problem-specific concept: Dynamic Programming

This is a simplified example of a dynamic programming problem. We calculate the Fibonacci sequence, which is a common introductory problem for dynamic programming.

1
2
3
4
5
6
7
8
def fibonacci(n, memo={}):
    if n <= 1:
        return n
    elif n not in memo:
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))  # It will print 55

Integrating the drills:

The final solution uses all of these concepts.

We use iteration to loop through the list of numbers.
Inside this loop, we use comparison operations and conditional branching to check if a number is greater than the previous one and whether to continue with the current sequence or start a new one.
We use recursion to calculate all possible subsequences starting from each number.
We use data storage and retrieval to store the lengths of the longest subsequences found so far, and the number of such subsequences. We then retrieve this information to compare with new subsequences we find.
Finally, we use dynamic programming to avoid redundant computation by storing and reusing previously computed results.

Q&A

Does anybody know how to solve this using segment tree?

Yes, it’s possible to solve this problem using a segment tree, but it might be a bit overkill and also harder to implement and understand, especially for beginners.

Segment trees are data structures that allow processing range queries and updating array values in logarithmic time. In our case, we could potentially use a segment tree to keep track of the longest increasing subsequence (LIS) and the count of such subsequences up to each position in the array.

Here’s a rough sketch of how it might look:

First, we sort the numbers and their indices.
We initialize a segment tree, where each node represents a range of indices in the sorted array and stores two values: the length of the longest increasing subsequence ending at this range, and the count of such subsequences.
Then we process the sorted numbers in ascending order. For each number, we use the segment tree to find the longest subsequence ending with a smaller number, and extend this subsequence by the current number. We update the node corresponding to the current number’s index in the tree.
When updating a node in the tree, we may need to recalculate the values stored in its parent nodes, up to the root. This is where the segment tree shines: we can do this efficiently in logarithmic time.
After processing all numbers, the root of the tree will contain the length of the overall LIS and the count of such subsequences.

However, note that this approach would work for finding the LIS in general, not specifically for finding the number of subsequences of the longest length. For that, you would need to modify the update process to also keep track of the count of subsequences.

In summary, while a segment tree could theoretically be used for this problem, it’s probably not the most suitable tool. It would require careful implementation and understanding of the intricacies of segment trees, and the resulting solution might not be very intuitive or easy to understand. The dynamic programming approach is a lot simpler and more straightforward.

Given nums = [1,2,3,1,2,3] The expected output is 4, is this how the 4 would be composed? 123123 123123 123123 123123

Your input and expected output seems to be slightly misunderstood. The input is nums = [1,2,3,1,2,3] and the expected output is 4 because there are 4 longest increasing subsequences of length 3. They are:

[1,2,3] from indices 0,1,2
[1,2,3] from indices 0,1,5
[1,2,3] from indices 0,4,5
[1,2,3] from indices 3,4,5

These subsequences are distinct and have the maximum length among all increasing subsequences in the given list, hence the output 4.

When you see nums.length <= 2000, problem solved. Use DP.

Yes, when you see that the length of the array nums is reasonably small (e.g., nums.length <= 2000), it is a strong hint that a dynamic programming (DP) approach could be a good fit for solving the problem.

The reason is that DP algorithms often have time complexities proportional to the square or cube of the input size, making them feasible for relatively small inputs. In this case, the time complexity would be O(n^2), where n is the length of the nums array, which is manageable for n <= 2000.

DP is well-suited for problems like this one, where the solution involves making choices at each step that depend on previous choices. In this problem, we keep track of the length and count of the longest increasing subsequence up to each point in the array. We can then build up the solution for the whole array by extending the solutions for the shorter subsequences.

Remember, just seeing a small upper bound on the input size is not enough to immediately conclude that DP should be used. It’s essential to understand the problem and identify overlapping subproblems and an optimal substructure, which are key characteristics of problems that can be solved efficiently with DP.

Why there is no modulo 10^9+7. For example this testcase clearly has 2^34 different subsequences:

[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34] Yes, testing system accepts this as a valid testcase but doesn’t return anything, expected output is nothing, and all testcases’ results are Wrong Answer.

The lack of a modulo operation in this problem is likely because the problem setter did not anticipate such large numbers of sequences. Indeed, for most problems on competitive programming platforms, especially those involving count or the number of ways, you’ll often see a requirement to return the answer modulo 10^9+7, to avoid overflow and keep the numbers manageable.

However, for the test case you provided, the number of longest increasing subsequences (LIS) is not 2^34. The longest increasing subsequence for the given list is not unique and can be formed in many ways, but we are interested in finding the number of such longest increasing subsequences.

Each number appears twice in the list, so for every pair (x, y) with x < y, there are four options:

Neither x nor y is included in the LIS.
Only x is included.
Only y is included.
Both x and y are included.

So, there are 4^(n/2) possible sequences, where n is the length of the input list.

As you pointed out, this can still result in large numbers. Depending on the platform and problem settings, this may cause overflow issues if not handled properly. However, it’s possible that the test system does not fully handle such large inputs, which is why you’re not seeing an expected output.

For large-scale test cases like this, it’s crucial to design an efficient solution and potentially use modulo arithmetic to avoid overflow issues. If you expect to handle cases where the count is extremely large (close to or exceeding the maximum limit of an integer), you should consider using a modulo operation.

Is there a way we can apply DP to the recursion solution of this problem? I tried the recursion but could not apply DP, can someone help me out here. My solution is as follows (PS: It works but gives a TLE)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    int res=0;
    int longest_sequence=0;
    int solve(vector<int>& a, int ans, int curr, int prev, vector<vector<int>>& dp){
        if(curr == a.size()){
            if(ans > longest_sequence){
                res = 1;
                longest_sequence = ans;
            } else if(ans == longest_sequence){
                res++;
            }
            // cout << "Longest Sequence Length: " << longest_sequence << endl;
            return 0;
        }

        // include
        int inc = 0;
        if(prev==-1 || a[curr] > a[prev]){
            inc = 1 + solve(a, ans+1, curr+1, curr, dp);
        }

        // exclude
        int exc = solve(a, ans, curr+1, prev, dp);

        return dp[curr][prev+1] = max(exc, inc);
    }
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> v;
        vector<vector<int>> dp(n, vector<int>(n+1, -1));

        int longest_sequence_length = solve(nums, 0, 0, -1, dp);
        for(auto it:dp){
            for(auto i:it){
                cout << i << " ";
            } cout << endl;
        }

        return res;
    }
};

The TLE (Time Limit Exceeded) issue you are experiencing is because the recursion is not using previously calculated solutions, causing redundant computations. Although you have the DP table in your code, it’s not correctly utilized, which is why the recursion is not taking advantage of it. Working solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int N = nums.size();
        if (N <= 1) return N;
        vector<int> lengths(N, 0); 
        vector<int> counts(N, 1); 

        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < j; ++i) {
                if (nums[i] < nums[j]) {
                    if (lengths[i] >= lengths[j]) {
                        lengths[j] = lengths[i] + 1;
                        counts[j] = counts[i];
                    } else if (lengths[j] == lengths[i] + 1) {
                        counts[j] += counts[i];
                    }
                }
            }
        }

        int longest = *max_element(lengths.begin(), lengths.end());
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            if (lengths[i] == longest) {
                ans += counts[i];
            }
        }
        return ans;
    }
};

It uses two vectors, lengths and counts. lengths[i] represents the length of the longest increasing subsequence (LIS) ending at i, and counts[i] represents the number of LISs ending at i. The time complexity is O(N^2), where N is the length of nums.

Below is a Python version of a DP solution, which you can then translate into C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findNumberOfLIS(self, nums):
        N = len(nums)
        if N <= 1: return N
        lengths = [0] * N #lengths[i] = length of longest ending in nums[i]
        counts = [1] * N #count[i] = number of longest ending in nums[i]

        for j, num in enumerate(nums):
            for i in range(j):
                if nums[i] < nums[j]:
                    if lengths[i] >= lengths[j]:
                        lengths[j] = 1 + lengths[i]
                        counts[j] = counts[i]
                    elif lengths[i] + 1 == lengths[j]:
                        counts[j] += counts[i]

        longest = max(lengths)
        return sum(c for l, c in zip(lengths, counts) if l == longest)

Here is how it works:

Two lists, lengths and counts, are initialized. lengths[i] represents the length of the longest increasing subsequence (LIS) ending at i, and counts[i] represents the number of LISs ending at i.
For each number, we look at all the numbers before it. If the current number is greater, we potentially have a new sequence, so we update our lengths and counts.
We increment the length for the current number and set the count to be the same as the count of the previous number. If we have seen this length before, we add the count of the previous number.
Finally, we return the sum of counts of all lengths that are equal to the maximum length.

This solution has a time complexity of O(N^2), where N is the length of nums. This is because for each number, we perform a loop operation on all numbers before it. However, this is a significant improvement over the recursive solution without memoization, which has an exponential time complexity.

I was trying to solve it using the traditional take and skip dp.

Ah, you’re approaching this with the classic recursion-based way of thinking: either take or skip an element, which is the foundation of many dynamic programming problems. However, this problem is more intricate because not only do you need to keep track of the longest increasing subsequence, but also count the maximum number of such subsequences.

The main issue with your code is that you’re trying to solve it purely recursively, without using the benefits of dynamic programming to store and reuse the results of subproblems. Your current solution is a depth-first search (DFS) with a lot of overlapping subproblems, which leads to a high time complexity and eventually a TLE (Time Limit Exceeded) error.

We could potentially store the answers for the subproblems in a dynamic programming table. However, we need to carefully define our state. For this problem, a state could be defined by two parameters: the end index of the subsequence and the length of the subsequence. But, for the ’take’ scenario, we need an additional check to ensure the subsequence remains increasing.

Unfortunately, adapting your current code to use dynamic programming isn’t straightforward because the recursion happens in multiple places (during the include and exclude scenarios). In fact, this problem is typically solved using a different dynamic programming approach, as shown in previous responses.

This doesn’t mean that your initial intuition was entirely wrong, just that for this problem, the ’take or skip’ approach doesn’t easily translate into an efficient dynamic programming solution. It’s great to keep trying different ways to solve a problem, as it ultimately deepens your understanding of dynamic programming and other techniques!

Can someone point out why is it failing for this testcase: Output is 0 ,expected 1087680

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int solve(int index,int prevIndex,vector<int> &nums,vector<int> &ds,
                    vector<int> &cnt,vector<vector<int>> &dp){
        //base case
        if(index>=nums.size()){
            cnt[ds.size()]++;
            return 0;
        }
        if(dp[index][prevIndex+1]!=-1){
            return dp[index][prevIndex+1];
        }

        int take=INT_MIN;
        if(prevIndex==-1 || nums[prevIndex]<nums[index]){
            ds.push_back(nums[index]);
            take=1+solve(index+1,index,nums,ds,cnt,dp);
            ds.pop_back();
        }

        int notTake=solve(index+1,prevIndex,nums,ds,cnt,dp);
        return dp[index][prevIndex+1] = max(take,notTake);
    }
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> cnt(n+1,1); // to cnt all LIS
        vector<int> ds;

        vector<vector<int>> dp(n+1,vector<int>(n+2,-1));
        int largestLen = solve(0,-1,nums,ds,cnt,dp);

        return cnt[largestLen];
    }
};

The key mistake in your solution is the way you’re counting the longest increasing subsequences (LIS). In your current approach, cnt[ds.size()]++ gets incremented each time the recursion reaches the end of the array, without checking whether the sequence is increasing or not.

Here’s a revised version of your function with the correct logic for counting:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int solve(int index, int prevIndex, vector<int> &nums, vector<int> &ds, vector<int> &cnt, vector<vector<int>> &dp, int &max_len){
        //base case
        if(index >= nums.size()){
            max_len = max(max_len, (int)ds.size()); // update the maximum length found
            return 0;
        }

        if(dp[index][prevIndex + 1] != -1){
            return dp[index][prevIndex + 1];
        }

        int take = INT_MIN;
        if(prevIndex == -1 || nums[prevIndex] < nums[index]){
            ds.push_back(nums[index]);
            take = 1 + solve(index + 1, index, nums, ds, cnt, dp, max_len);
            ds.pop_back();
        }

        int notTake = solve(index + 1, prevIndex, nums, ds, cnt, dp, max_len);
        return dp[index][prevIndex + 1] = max(take, notTake);
    }

    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> cnt(n + 1, 0); // initialize cnt with 0
        vector<int> ds;
        int max_len = 0;

        vector<vector<int>> dp(n + 1, vector<int>(n + 2, -1));
        solve(0, -1, nums, ds, cnt, dp, max_len);

        return cnt[max_len];
    }
};

In the revised version, I’m maintaining max_len to keep track of the maximum length found during the recursion. Whenever the recursion hits the base case, it updates max_len if the current length (ds.size()) is greater. This helps to get the length of the longest increasing subsequence. And when it hits the base case, it increments cnt[ds.size()], meaning that it’s found an increasing subsequence of that length. Note that the vector cnt has been initialized with 0s, not 1s.

Remember to take care of this case: when nums[prevIndex] < nums[index] you can consider the current number as part of the subsequence, but only then.

[1,1,2,2,2], Expected 6 why?, i dont get it

[1, -, 2, -, -] [1, -, -, 2, -] [1, -, -, -, 2] [-, 1, 2, -, -] [-, 1, -, 2, -] [-, 1, -, -, 2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class FT:
    '''
    Used map<int,int> instead of BIT_arr
    Stores num:lis
    The get function allows us to query all numbers < given number, so that we get the max(lis) of them. Adding 1 to them will give us the lis of current num.
    '''
    def __init__(self):
        self.size = 2000001
        self.arr = {}
    def put(self, num, lis):
        num+=1000001
        while num <= self.size:
            self.arr[num] = max(lis, self.arr.get(num, 0))
            num+=num&-num
    def get(self, num):
        num+=1000001
        ret = 0
        while num > 0:
            ret = max(ret, self.arr.get(num, 0))
            num-=num&-num
        return ret
class Lis_FT:
    '''
    As per the constraint, the lis ranges from 1, 2000
    And to get the no. of subsequences ending at particular index with some particular lis, a separate instance of this class is created in lazy fashion for all lis in range[1, 2000]
    Eg: nums: [1, 2, 3, 1000, 4, 5]
        At index 5, 
            Q1: LIS = 5, how?
                LISes with length 4: [1, 2, 3, 4], [1, 2, 3, 1000]
                Note: Range query helps us to avoid [1, 2, 3, 1000]
            Q2: how many LISes are there with length 5 = LISes count with length 4
            LISes with length 4 are [1,2,3,1000], [1,2,3,4], but 5 cannot be appeneded to [1,2,3,1000], again we need one more FT separately for LIS 4 where index:val -> num: LISes count, to avoid the [1,2,3,1000].
    '''
    def __init__(self):
        self.size = 2000001
        self.arr = {}
    def put(self, num, count):
        num+=1000001
        while num <= self.size:
            self.arr[num] = self.arr.get(num, 0) + count
            num+=num&-num
    def get(self, num):
        num+=1000001
        ret = 0
        while num > 0:
            ret += self.arr.get(num, 0)
            num-=num&-num
        return ret
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        ans = [0, 0]
        ft = FT() # num: LIS
        lis_ft = {} # value => num: No. of LIS
        def get_count(lis, num):
            if lis not in lis_ft:
                lis_ft[lis] = Lis_FT()
            lis_ft_ob = lis_ft[lis]
            return lis_ft_ob.get(num-1)
        for num in nums:
            lis = ft.get(num-1)
            count = 1 if lis == 0 else get_count(lis, num)

            ft.put(num, lis+1)
            if lis+1 not in lis_ft:
                lis_ft[lis+1] = Lis_FT()
            lis_ft[lis+1].put(num, count)

            if ans[0] < lis:
                ans[0] = lis
                ans[1] = count
            elif ans[0] == lis:
                ans[1] += count
        return ans[1]

This is a Python class and method for finding the number of longest increasing subsequences (LIS) in a list of integers.

The script has 3 classes:

FT: This class represents a data structure known as a Fenwick Tree, also called a Binary Indexed Tree (BIT). This is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. It is particularly useful for performing these operations on a dynamic set of values, such as the numbers in an array as it changes over time. Here, it’s used to store the length of the longest increasing subsequence (LIS) ending at each index of the input array.
Lis_FT: This class is another implementation of Fenwick Tree used for storing the count of LIS for each index in the input array.
Solution: This is the main class with a method findNumberOfLIS(self, nums: List[int]) -> int which uses instances of the FT and Lis_FT classes to calculate the number of longest increasing subsequences in the input list nums.

Here is a brief description of how the findNumberOfLIS method works:

For each number in the input list, it calculates the length of the longest increasing subsequence (LIS) that ends at that number using the FT instance ft.
It then gets the count of such LISes ending at that number from the Lis_FT instance lis_ft. If the length of the LIS is 0, it sets the count to 1, otherwise, it gets the count from lis_ft.
Next, it updates the ft and lis_ft instances with the new LIS length and count for the current number.
Finally, it updates the answer ans if the current LIS length is greater than the previous maximum LIS length or if it’s equal to the previous maximum but the count is larger.

The method returns the count of the longest increasing subsequences in the input list.

Please note that this is a complex algorithm that utilizes advanced data structures. If you’re not familiar with Fenwick Trees, it might be difficult to understand all the details. But, essentially, it’s using these data structures to efficiently calculate and update the lengths and counts of the longest increasing subsequences as it iterates over the input list.

Is the sequence not a subsequence?

Yes, a sequence is a subsequence of itself. The concept of subsequences includes both proper subsequences and the sequence itself.

For instance, let’s take an array arr = [1, 2, 3]. Here are all its subsequences:

[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

The last subsequence, [1, 2, 3], is the same as the original sequence. It’s considered a subsequence because it meets the definition: a subsequence of a sequence is a sequence that can be derived from the original sequence by deleting zero or more elements without changing the order of the remaining elements.

So, in your problem, when you’re counting the longest increasing subsequences, it includes the longest increasing sequence itself if it exists.

ou can solve it with patience sort that’s better optimized for speed than the dp solution. Here’s my code that’s in the top 95%.

Although I’m in the bottom 20% of memory and technically my solution is O(n^2). So if anyone as any tips it would be greatly appreciated!!!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        piles = [[(nums[0], 1)]]

        for num in nums[1:]:
            idx = bisect_left(piles, num, key=lambda x: x[-1][0])
            lis_count = 0

            if 0 <= idx - 1:
                for i in reversed(range(len(piles[idx - 1]))):
                    if piles[idx - 1][i][0] >= num: break
                    lis_count += piles[idx - 1][i][1]
            else:
                lis_count = 1
            
            if idx == len(piles):
                piles.append([(num, lis_count)])
            else:
                piles[idx].append((num, lis_count))
        
        return sum(piles[-1][i][1] for i in range(len(piles[-1])))

answer can be more than INT_MAX or even LLONG_MAX in c++. This question needs correction. answer should have been % 1e7.

The LeetCode problem statement does not mention the necessity of applying a modulo operation to the result. Also, it is important to note that the problem statement clearly mentions the constraints on the input: “The length and the number of the input list will not exceed 2000.” Given this constraint, the result will fit into the range of a standard int in C++ or int in Python, so there is no need to apply a modulo operation.

In certain competitive programming problems, when the output can be very large, the problem statement typically requests the output modulo 10^9+7 to avoid overflow. But in this case, the constraints ensure that the result will not overflow an int.

As for the test case you’ve provided, it seems to be outside the constraints specified in the problem statement. In such situations, it’s common to consult the problem’s constraints to ensure the input is valid. Please double-check the constraints next time. If you believe there is an error in the problem statement, you can usually report it directly to the platform’s administrators or through a designated reporting feature.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def findNumberOfLIS(self, nums):
        n = len(nums)
        length = [0] * n
        count = [0] * n

        def calculate_dp(i):
            if length[i] != 0:
                return

            length[i] = 1
            count[i] = 1

            for j in range(i):
                if nums[j] < nums[i]:
                    calculate_dp(j)
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1
                        count[i] = 0
                    if length[j] + 1 == length[i]:
                        count[i] += count[j]

        max_length = 0
        result = 0
        for i in range(n):
            calculate_dp(i)
            max_length = max(max_length, length[i])

        for i in range(n):
            if length[i] == max_length:
                result += count[i]

        return result

What’s the point of the calculate_dp(j) call since we are already iterating through all values from 0 to n?

The function calculate_dp(j) is used to calculate the length of the longest increasing subsequence (LIS) ending at index j and the count of such subsequences. These are stored in length[j] and count[j], respectively.

This function call inside the loop plays a key role in implementing the dynamic programming (DP) approach to this problem. It ensures that the necessary DP values are calculated before they are used.

Let’s look at a particular situation. When we’re at index i and considering if we should append the current number to the LIS that ends at index j (j < i), we need to know two things:

The length of the LIS ending at j (stored in length[j]).
The count of such LISs (stored in count[j]).

Since we are moving forward in the array, we calculate these values for all indices less than i and store them in the length and count arrays.

So, when the function calculate_dp(j) is called, it checks if length[j] is already calculated. If it isn’t (i.e., length[j] is 0), the function will calculate it using the same process, considering all indices less than j.

This is a common practice in dynamic programming to ensure that we have all the necessary calculated states before they are used. This technique is also referred to as “memoization” in computer science, which is the act of storing the results of expensive function calls and reusing them when the same inputs occur again. This is the key idea that makes dynamic programming efficient.

For those of you that prefer to use recursion and build a cache ontop of it (which is more my style), here you go. Just keep in mind doing the the n^2 cache is probably better.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    public int findNumberOfLIS(int[] nums) {
        int[] res = helper(nums, 0, Integer.MIN_VALUE, new HashMap<Integer, HashMap<Integer, int[]>>());
        // {length, count}
        return res[1];
    }
    
    private int[] helper(int[] nums, int idx, Integer prev, HashMap<Integer, HashMap<Integer, int[]>> cache) {
        if (idx >= nums.length)
            return new int[] {0, 1};

        // idx -> prev -> {result}
        if (cache.containsKey(idx) && cache.get(idx).containsKey(prev))
            return cache.get(idx).get(prev);
        
        int[] skipNum = helper(nums, idx + 1, prev, cache);
        int[] res = new int[2];
        int[] finalResult;
        if (prev == Integer.MIN_VALUE || nums[idx] > prev) { // eligile to take number
            int[] takeNum = helper(nums, idx + 1, nums[idx], cache);
            if (takeNum[0] + 1 > skipNum[0]) {
                res[0] = takeNum[0] + 1;
                res[1] = takeNum[1];
                finalResult = res;
            } else if (skipNum[0] > takeNum[0] + 1) {
                finalResult = skipNum;
            } else {
                res[0] = skipNum[0];
                res[1] = skipNum[1] + takeNum[1];
                finalResult = res;
            }
        } else {
            finalResult = skipNum;
        }
        
        if (!cache.containsKey(idx))
            cache.put(idx, new HashMap<>());
        cache.get(idx).put(prev, finalResult);
        
        return finalResult;
    }

This solution adopts a top-down dynamic programming (DP) approach, also known as memoization, to solve the problem. It uses recursion to break down the problem into smaller subproblems, and uses a cache (in this case, a nested HashMap) to store the results of these subproblems to avoid repeating calculations.

Let’s understand the code:

The findNumberOfLIS function is the entry point, it calls the helper function with initial parameters: index as 0 and the previous number as Integer.MIN_VALUE (which serves as a placeholder since there’s no previous number at the start).
The helper function is where the actual processing happens. It takes an index, a previous number, and a cache as input. It tries to find the longest increasing subsequence (LIS) starting from the current index and the count of such sequences.
If the current index (idx) is out of bounds (i.e., idx >= nums.length), we’ve reached the end of the array, and the base case returns {0, 1}, meaning that the length of LIS is 0 and the count is 1 (an empty sequence is considered a valid increasing subsequence).
The code then checks if the result for the current index and previous number is already stored in the cache. If it is, it returns the cached result. This step is crucial as it prevents recalculating the same subproblems, thus improving efficiency.
skipNum represents the scenario where we skip the current number (nums[idx]) and try to find the LIS from the rest of the array. This is obtained by calling helper(nums, idx + 1, prev, cache).
If the current number is greater than the previous number (or if the previous number is Integer.MIN_VALUE, which only happens at the start), we can choose to take the current number. takeNum represents this scenario where we include the current number in our sequence and try to find the LIS from the rest of the array. This is obtained by calling helper(nums, idx + 1, nums[idx], cache).
The code then compares takeNum and skipNum. If the length of the LIS when including the current number (takeNum[0] + 1) is greater than the length when skipping it (skipNum[0]), we choose to include it (finalResult = res). If it’s less, we choose to skip it (finalResult = skipNum). If they are equal, we can either take it or skip it, and we sum the counts of both scenarios (res[1] = skipNum[1] + takeNum[1]; finalResult = res).
The final result for the current index and previous number is then stored in the cache and returned.

This approach shares the same key insight with the bottom-up DP approach: at each step, we can choose to either take the current number (if it’s greater than the previous number) or skip it. The difference lies in the order of calculation (top-down versus bottom-up) and how subproblem results are stored and reused (recursion with memoization versus iteration with DP table).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> length(n,1);
        vector<int> count(n,1);
        for(int i=1; i < n; i++){
            for(int j=0; j < i; j++){
                if(nums[j] < nums[i]){
                    if(length[j] + 1 > length[i]){
                        length[i]=length[j]+1;
                        count[i]=0;
                    }
                    if(length[j]+1==length[i]) count[i]+=count[j];
                }
            }
        }
        int maxLength= *max_element(length.begin(),length.end());
        int result=0;
        for(int i=0; i < n; i++){
            if(length[i]==maxLength) result+=count[i];
        }
        return result;
    }
};

This solution is a standard dynamic programming (DP) approach to the problem.

Let’s break it down:

Two vectors length and count of size n are initialized to all 1s. The length array is used to keep track of the longest increasing subsequence ending at each index, while the count array is used to count the number of such longest increasing subsequences. Initially, each element is its own longest increasing subsequence, so the length and count are both 1.
For each index i from 1 to n-1, the code checks all the previous elements j from 0 to i-1. If nums[j] < nums[i], it means nums[i] can be appended to the increasing subsequence ending at j.
- If length[j] + 1 > length[i], it means we have found a longer increasing subsequence ending at i. So, we update length[i] with length[j] + 1 and reset count[i] because we have found a new longest subsequence.
- If length[j] + 1 == length[i], it means we have found another longest increasing subsequence ending at i. So, we add count[j] to count[i] because now we have more ways to form the longest subsequence.
After the two loops, length[i] is the length of the longest increasing subsequence ending at i, and count[i] is the number of such subsequences.
We find the maximum length from the length array. This is the length of the longest increasing subsequence in nums.
Finally, we traverse the length and count arrays again. If length[i] equals the maximum length, we add count[i] to the result, because these are the longest increasing subsequences.
The final result is the total number of longest increasing subsequences in nums.

This solution works because it systematically checks all possible subsequences and keeps track of the necessary information along the way. Its time complexity is O(n^2) because of the nested loops, and its space complexity is O(n) because of the length and count arrays.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
INF=float('inf')
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        ll=len(nums)
        @functools.cache
        def dp(prev,i):
            if i>=ll:
                return 0,1
            take,take_count=0,0
            if nums[i]>prev:
                take,take_count=dp(nums[i],i+1)
                take+=1
            ignore,ignore_count=dp(prev,i+1)
            if take==ignore:
                return take,take_count+ignore_count
            if take>ignore:
                return take,take_count
            return ignore,ignore_count
        res,res_count=dp(-INF,0)
        return res_count

can you explain the if-else clause? thanks

Here is what each of those if-else conditions is doing:

if nums[i]>prev: This condition checks if the current number in the array nums at index i is greater than the previous number. If it is, then it implies that the current number can be part of an increasing subsequence. So it calls the dp(nums[i], i+1) function which considers the current number as part of the sequence (that’s why nums[i] is passed as prev to the dp function), and moves to the next number (that’s why i+1 is passed). The result of this operation is stored in take, take_count where take represents the length of the longest increasing subsequence considering nums[i] and take_count is the count of such subsequences. Since nums[i] is included, take is incremented by 1 (take+=1).
ignore, ignore_count = dp(prev, i+1): This is the case where nums[i] is not included in the sequence. It just moves to the next number (i+1) keeping the prev value intact. The length of the longest increasing subsequence in this case is stored in ignore, and the count of such subsequences is stored in ignore_count.
if take==ignore: If the length of the longest increasing subsequence with or without including nums[i] is the same, then it returns that length (take or ignore), and the sum of the counts (take_count + ignore_count) since both possibilities are valid and contribute to the count of longest increasing subsequences.
if take>ignore: If the length of the longest increasing subsequence is greater when including nums[i] (take), then it returns take and take_count.
The final return ignore, ignore_count statement is executed when ignore > take, i.e., if ignoring nums[i] leads to a longer increasing subsequence. It then returns ignore and ignore_count.

The main idea here is to consider both possibilities - including or excluding the current number in the sequence - and update the maximum length and count accordingly. This way, it finds all the longest increasing subsequences in the array.

The following official statement is wrong.

If length[j]+1>length[i], it means we have found a longer subsequence ending at index ii. In this case, we update length[i] to length[j]+1. Additionally, we discard any subsequences we saw earlier since they are no longer LIS: reset count[i] to zero.

count[i] should be count[j]. since paths end at j(left) is propagated to i (right). we should not reset to zero. (Output of answer code is eventually correct but theory is wrong)

I understand your point. The statement from the official explanation you mentioned might have been misleading. The concept they’re trying to explain is correct, but the wording may have led to confusion.

Indeed, when they mention “reset count[i] to zero”, they mean that we should disregard any paths we’ve found that end at i so far. However, it doesn’t mean to “reset to zero”, rather it means that we update count[i] to the count of the longer subsequence found, which is indeed count[j].

So, if length[j] + 1 > length[i], it means a longer subsequence can be formed by adding the i-th number to the subsequence ending at j. In this case, length[i] should be updated to length[j] + 1, and count[i] should be updated to count[j] because the number of longest increasing subsequences ending at i would be the same as the number of such subsequences ending at j.

Thanks for pointing this out. It’s important to have clear and correct explanations, especially in a learning context.

for those guys who are not quite familiar with this type of problem, please also check No.549. Binary Tree Longest Consecutive Sequence II to have a better understanding.. for each element in the array or on in the tree, they all carry three fields :

the maximum increasing / decreasing length ends at the current element,
its own value ,
the total number of maximum length, and each time when we visit a element, we will use its 2) to update 1) and 3), the only difference is for array we use iteration while for tree we use recursion…… Also, for substring problem, we usually use only one for loop because for each index, we only care about the relationship between its two neighbors, while for subsequence problem, we use two for loops , because for each index, any other indexes can do something…

Thank you for your contribution. It’s always helpful to understand the underlying patterns and similarities across different problems.

The problem “No.549. Binary Tree Longest Consecutive Sequence II” indeed shares a similar strategy with the Longest Increasing Subsequence (LIS) problem. Both involve dynamically tracking and updating the maximum sequence length and the count of such sequences.

To elaborate more on your points:

“Maximum increasing/decreasing length ends at the current element”: In these problems, it’s often useful to maintain information about the longest sequence (increasing or decreasing) that ends at each element. This allows us to build up solutions to the problem incrementally.
“Its own value”: In these problems, the value of the current element often determines how it can be added to existing sequences. For example, in the LIS problem, an element can only be added to an increasing sequence if its value is larger than the last value in the sequence.
“The total number of maximum length”: This is the actual answer we’re interested in for these problems. We need to track not only the length of the longest sequence, but also how many such sequences exist.

And your observation about the distinction between substring and subsequence problems is also very insightful. Indeed, in substring problems, elements have a fixed neighboring relationship, but in subsequence problems, any element could potentially influence any other element, leading to a need for nested loops or recursive structures. This makes subsequence problems more complex and often requires dynamic programming or similar techniques to solve efficiently.

do you know of any other problems in addition to this problem and 549 that can be solved using this concept?

Here are a few problems on LeetCode that are solved using similar concepts of dynamic programming and tracking the longest sequences or subsequences:

300. Longest Increasing Subsequence: This is the classic problem that requires finding the longest increasing subsequence. The techniques used in this problem are similar to the current problem.
673. Number of Longest Increasing Subsequence: This problem is the same as the one we discussed but asks for the number of longest increasing subsequences.
1143. Longest Common Subsequence: In this problem, we have two sequences and we need to find the length of their longest common subsequence.
516. Longest Palindromic Subsequence: Here, we are given a string and we need to find the length of the longest palindromic subsequence in the string.
198. House Robber: Here, we have a list of non-negative integers representing the amount of money of each house. We have to maximize the amount of money you can rob tonight without alerting the police, which means we cannot rob two adjacent houses.
213. House Robber II: This problem is a variant of the House Robber problem where the houses are in a circle, which means the first house is the neighbor of the last one.
646. Maximum Length of Pair Chain: In this problem, we have to find the longest chain which can be formed from a given set of pairs.
376. Wiggle Subsequence: The problem requires us to find the longest subsequence where the differences between consecutive numbers strictly alternate between positive and negative.
368. Largest Divisible Subset: Here, we need to find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
1048. Longest String Chain: In this problem, we are given a list of words with different lengths, arranged lexicographically, and we need to find the longest possible string chain.

These problems, while different in their specifics, all involve some form of sequence or subsequence where we’re tracking maximum or minimum lengths, counts, or sums, and often involve dynamic programming techniques.

I used map to record cnt before which was slower than using array directly, roughly 90ms -> 30ms

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int len = nums.length;
        // dp[i] means the lengh of LIS ending at i
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        // cnt[i] means # LIS ending at i
        int[] cnt = new int[len];
        
        int ret = 0, max = 1;
        for (int i = 0; i < len; i++) {
            int count = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (1 + dp[j] > dp[i]) {
                        count = cnt[j];
                        dp[i] = 1 + dp[j];
                    } else if (1 + dp[j] == dp[i]) {
                        count += cnt[j];
                    }
                }
            }
            cnt[i] = count;
            
            if (dp[i] > max) {
                ret = count;
                max = dp[i];
            } else if (dp[i] == max) {
                ret += count;
            }
        }
        return ret;
    }

The solution you provided is using a dynamic programming (DP) approach to solve the problem, which is generally more efficient than using a hashmap (map) for this particular problem.

In this solution, you’ve used two arrays: dp and cnt. The dp array is used to store the length of the Longest Increasing Subsequence (LIS) ending at each index, while the cnt array is used to store the number of LIS that end at each index.

The outer loop iterates over the array from left to right. For each number at index i, the inner loop iterates over all previous numbers. If the current number is larger than a previous number, it means that the current number can extend the LIS ending at the previous number.

If the extended sequence is longer than the current LIS ending at i (i.e., 1 + dp[j] > dp[i]), the dp and cnt at i are updated accordingly. If the extended sequence is as long as the current LIS ending at i (i.e., 1 + dp[j] == dp[i]), we add the count of LIS ending at j to the count of LIS ending at i.

Finally, you calculate the maximum length of LIS (max) and the total count of maximum length LIS (ret).

By replacing the map with arrays, you have significantly improved the time complexity of your solution because array access is usually faster than map access. Moreover, it also reduces the space complexity as you no longer need to store the keys. This explains the drop in runtime from 90ms to 30ms.

Good job on optimizing your solution!

Can some one please explain why we need to calculate the result using the below code:

if(max_len == len[i])res += cnt[i]; if(max_len < len[i]){ max_len = len[i]; res = cnt[i]; }

Why can’t we just return the last element of the count array( cnt )? Since we are calculating the number of longest increasing sub-sequence in cnt array.

The reason we cannot simply return the last element of the count array (cnt) is because the longest increasing subsequence (LIS) may not end at the last element. The cnt array keeps track of the number of LISs ending at each index in the original array. If the actual LIS ends before the last index, the last element in cnt will not give us the correct count of the LIS.

The logic you mentioned:

1
2
3
4
5
if(max_len == len[i])res += cnt[i];
if(max_len < len[i]){
    max_len = len[i];
    res = cnt[i];
}

is ensuring that res holds the count of the longest subsequence. This is done by iterating through the array and checking if the current element (len[i]) is equal to the maximum length found so far (max_len), in which case we add the count at that index to res. If the length at the current index is greater than the current max_len, it means we have found a longer subsequence. In that case, we update max_len and set res to the count of this new longest subsequence (cnt[i]).

This way, at the end of the iteration, res holds the count of the longest increasing subsequence, no matter where in the original array that subsequence ends.

QUOTE: len[i]: the length of the Longest Increasing Subsequence which ends with nums[i]. cnt[i]: the number of the Longest Increasing Subsequence which ends with nums[i].

COMMENTS: Great solution! I think it would be more clear to explain that len[i]/count[i] represents … right before nums[i]

I see what you’re saying. The explanation would indeed be clearer with an emphasis on the subsequence leading up to and ending at the index i in the array.

Here is a modified version of the original quote:

len[i]: the length of the Longest Increasing Subsequence that ends with nums[i]. This includes all elements right before nums[i] that constitute the subsequence.
cnt[i]: the number of Longest Increasing Subsequences that end with nums[i]. This refers to the count of distinct sequences including all elements right before nums[i] that form subsequences of the same maximum length.

In other words, len[i] and cnt[i] encapsulate the information about the longest subsequences up to index i, taking into account all possible subsequences that could end at nums[i].

I am not quite get the third if statement “else if(len[i] < len[j] + 1) {” How can a len[j] > len[i], i think the most gap between len[j] and len[i] is 1, so this condition should be actually len[i] == len[j]. Or am I wrong?

In the context of dynamic programming, it’s important to remember that we’re dealing with cumulative states – these states aren’t always updated incrementally by 1, but are determined by the history of each sub-problem. In this case, we’re looking for the longest increasing subsequence up to each index.

Let’s go through the three cases represented by the if-else block:

if(nums[i] > nums[j]): If the current number nums[i] is larger than nums[j], then it could extend the increasing subsequence ending at nums[j].
if(len[i] < len[j] + 1): If the longest increasing subsequence length ending at nums[i] (len[i]) is less than the longest increasing subsequence length ending at nums[j] plus 1 (len[j] + 1), then we’ve found a longer increasing subsequence ending at nums[i] by appending nums[i] to the subsequence ending at nums[j]. Thus, len[i] is updated to len[j] + 1.
else if(len[i] == len[j] + 1): If len[i] is equal to len[j] + 1, that means we’ve found another subsequence of the same maximum length ending at nums[i]. Thus, we increment the count for the longest subsequences ending at nums[i] by the count of longest subsequences ending at nums[j].

So, len[i] < len[j] + 1 is possible due to the nature of dynamic programming, which keeps updating len[i] as we find longer subsequences ending at nums[i].

Actually, your understanding isn’t correct in the context of this problem. This condition len[i] < len[j] + 1 is checking whether the longest increasing subsequence (LIS) ending at j plus 1 (which is considering adding the current element at i to the LIS ending at j) is longer than the current longest LIS ending at i.

The gap between len[i] and len[j] can certainly be more than 1. This is because len[i] and len[j] represent the lengths of the longest increasing subsequences ending at indices i and j respectively, and there’s no rule that the lengths of these subsequences can differ by at most 1.

Consider an example where nums = [9, 1, 3, 7, 5, 6, 7] and you are at i = 6 (nums[i] = 7). Suppose you have calculated len = [1, 2, 3, 3, 4, 1] till i = 5. Now you are at i = 6, the LIS ending at j = 5 and including nums[i] will be longer than the current LIS ending at i, i.e., len[j] + 1 > len[i] or len[i] < len[j] + 1.

So, the condition len[i] < len[j] + 1 is to check if you have found a longer increasing subsequence ending at i by adding the current number to the LIS ending at j.

For the input sequence {1,2,3,4,5,3,4}, even though the result is correct which is 1, I was expecting cnt[6] to be equal to 1 but it is 2.

Why is cnt[5] not equal to cnt[6]? I am missing something. Please clarify.

The array cnt stores the number of longest increasing subsequences (LIS) ending at each index i. When you see that cnt[5] is not equal to cnt[6], it means that the number of longest increasing subsequences ending at index 5 is different from the number of longest increasing subsequences ending at index 6.

Given the input {1,2,3,4,5,3,4}, let’s look at indices 5 and 6 specifically:

At index 5, the number is 3, and the LIS ending at index 5 are {1,2,3} and {1,2,3,4,5,3}. There are 2 of them, so cnt[5] = 2.
At index 6, the number is 4, and the LIS ending at index 6 is {1,2,3,4} and {1,2,3,4,5,3,4}. There are also 2 of them, so cnt[6] = 2.

Note that although both cnt[5] and cnt[6] are 2, the actual subsequences counted are different. For cnt[6], we have {1,2,3,4} and {1,2,3,4,5,3,4}. These are different from the subsequences counted at cnt[5].

The final result of the function is the sum of counts where the length of the LIS is maximum, not the count at the last index of the input. In this case, the length of the LIS is 5 (which occurs for {1,2,3,4,5}), and there’s only one such sequence, so the result is 1.

one point I don’t understand is that, if(len[i] == len[j] + 1)cnt[i] += cnt[j]; why it must be the condition len[i] == len[j] + 1 I’m wondering why len[i] > len[j] doesn’t work?

The condition len[i] == len[j] + 1 is used to determine if we can append the current number to the subsequence ending at j, thus forming a longer subsequence.

len[i] represents the length of the longest increasing subsequence (LIS) ending at i, while len[j] is the length of the LIS ending at j. If len[i] == len[j] + 1, it means that the longest subsequence ending at i is the subsequence ending at j plus the element at index i. In this case, we add the count of the longest subsequences ending at j to the count at i, because all those subsequences have now been extended by nums[i].

On the other hand, if len[i] > len[j], it implies that the current number has already been appended to a longer subsequence than the one ending at j. So, we don’t count those subsequences ending at j, because they are not part of the longest subsequences ending at i.

In essence, len[i] == len[j] + 1 captures the exact condition when nums[i] can extend the LIS ending at j, and we need to update the count of LIS at i accordingly.

In the context of this problem, we’re looking for strictly increasing subsequences. If nums[i] == nums[j], then adding nums[i] to a subsequence that already contains nums[j] would not yield a strictly increasing subsequence, which is why we don’t need to handle this case.

Remember, a subsequence is increasing if every element is strictly greater than the previous one. If two elements are equal, the sequence is not strictly increasing, so we can skip considering these when looking for the longest increasing subsequence.

However, if the problem statement was looking for non-decreasing subsequences (where the sequence can stay the same or increase), then we would need to consider the case where nums[i] == nums[j].

if(max_len == len[i])res += cnt[i]; if(max_len < len[i]){ max_len = len[i]; res = cnt[i]; } can you explain why did you use above code

This piece of code is used to track the maximum length of the longest increasing subsequence (max_len) found so far, and to count the number of such subsequences (res).

Here’s a more detailed breakdown of the logic:

if(max_len == len[i])res += cnt[i];: If the length of the longest increasing subsequence ending at nums[i] (len[i]) is the same as the current longest length we’ve found so far (max_len), then we add the number of such subsequences (cnt[i]) to our count (res). This is because we’ve found another subsequence of the same maximum length.
if(max_len < len[i]){ max_len = len[i]; res = cnt[i]; }: If the length of the longest increasing subsequence ending at nums[i] is greater than the current longest length we’ve found (max_len), then we’ve found a new maximum length, so we update max_len to this new length (len[i]). Also, since this is a new maximum length, we reset our count (res) to the number of such subsequences (cnt[i]).

The end result of these computations is that res contains the number of longest increasing subsequences in the input array, which is the answer we return from this function.

Can anyone explain the reasoning behind the code below?

if(len[i] == len[j] + 1)cnt[i] += cnt[j];
      if(len[i] < len[j] + 1){
          len[i] = len[j] + 1;
          cnt[i] = cnt[j];
      }
}

If length[j]+1>length[i], it means we have found a longer subsequence ending at index i.

Why do we need to + 1? When length[i] < length[j], haven’t we already found a longer subsequence?

The reason we’re checking length[j] + 1 > length[i] instead of length[j] > length[i] is because we’re evaluating the possibility of extending the longest increasing subsequence that ends at index j by including the element at index i. The +1 is to account for the addition of the ith element to the subsequence.

In other words, we’re asking: If we add the ith element to the end of the longest increasing subsequence that ends at j, is this new sequence longer than the current longest increasing subsequence that ends at i?

If length[j] + 1 > length[i], then yes, it’s beneficial to add the ith element to the subsequence that ends at j, so we update length[i] to length[j] + 1.

If we only checked length[j] > length[i], we would not be taking into consideration the potential benefit of adding the ith element to the sequence ending at j.

Let’s consider the list nums = [1, 2, 4, 3, 5, 4, 7, 2].

The length array is used to keep track of the length of the longest increasing subsequence (LIS) ending at each position. For the nums list above, the length array would look like this after the algorithm is run: length = [1, 2, 3, 3, 4, 4, 5, 2].

Each entry length[i] is calculated by considering all previous entries length[j] (where j < i and nums[j] < nums[i]) and adding 1 to the maximum such length. This is because, if nums[j] < nums[i], then the sequence ending at position i could potentially be extended by the number at position j.

Here’s a visualization:

nums   = [1, 2, 4, 3, 5, 4, 7, 2]

length = [1, 2, 3, 3, 4, 4, 5, 2]

// step-by-step
1. length[0] = 1 (base case)
2. length[1] = max(length[0])+1 = 2 (since nums[0] < nums[1])
3. length[2] = max(length[0], length[1])+1 = 3 (since nums[0] < nums[2] and nums[1] < nums[2])
4. length[3] = max(length[0], length[1])+1 = 3 (since nums[0] < nums[3] and nums[1] < nums[3])
5. length[4] = max(length[0], length[1], length[2], length[3])+1 = 4 (since nums[0] < nums[4], nums[1] < nums[4], nums[2] < nums[4], and nums[3] < nums[4])
...

And so on.

The point here is that, at each step i, we’re looking at all the lengths of increasing subsequences ending at previous indices j (j < i), and seeing if we can extend those sequences with the ith element. We only consider the extension if nums[j] < nums[i], which would make the subsequence increasing.

We don’t just compare length[j] to length[i], but length[j] + 1 to length[i], because we’re considering the potential extension of the jth sequence by the ith element.

What’s the point of the calculate_dp(j) call since we are already iterating through all values from 0 to n? Since we are iterating from 0 to n in the outer for loop, everytime we are going to call calculate_dp(j) we are going to get a value that is already computed. Is the line added in order for it to work in top-bottom manner i.e. starting from n?

The calculate_dp(j) function call is actually necessary for the bottom-up approach to dynamic programming used in this problem.

Even though the outer loop iterates through all values from 0 to n, the inner loop does the same but up to the current value of i. So, when we call calculate_dp(j), we might be calculating it for j that is less than the current i.

The reason for the bottom-up approach and these function calls is to ensure that we have all necessary sub-problems solved before solving the problem for the current i. This is why we calculate dp[j] for all j < i before calculating dp[i].

Yes, calculate_dp(j) would have been computed already if j < i due to the outer loop, and the calculated values are used to build up the solutions to larger sub-problems. But this function call ensures that we have a valid dp[j] value to use in our calculations for dp[i].

Remember that dynamic programming relies heavily on overlapping sub-problems and optimal substructure, and the function call calculate_dp(j) is a way to ensure that we’re correctly leveraging previously calculated sub-problems to solve the current sub-problem.

For the input [1,3,5,4,7,1,3,5,4,7,1,3,5,4,7] isn’t the longest sub sequence [1,3,4,5,7]? This would occur twice. But it’s showing 6 as the expected output. Am I missing something here?

In the given input [1,3,5,4,7,1,3,5,4,7,1,3,5,4,7], the longest increasing subsequence is indeed [1,3,4,5,7]. However, there are multiple instances of such subsequences in the list, not just two.

The question asks for the total number of longest increasing subsequences. In your array, the subsequences [1,3,4,5,7] occur 6 times in total. They are formed from the following indices:

0,1,3,4,7
5,6,8,9,12
5,6,8,9,13
10,11,13,14,17
10,11,13,14,18
10,11,13,14,19

So, the correct output should be 6.