Solution
Approach 1: Dynamic Programming
Intuition and Algorithm
Suppose for sequences ending at nums[i]
, we knew the length length[i]
of the longest sequence, and the number count[i]
of such sequences with that length.
For every i < j
with A[i] < A[j]
, we might append A[j]
to a longest subsequence ending at A[i]
. It means that we have demonstrated count[i]
subsequences of length length[i] + 1
.
Now, if those sequences are longer than length[j]
, then we know we have count[i]
sequences of this length. If these sequences are equal in length to length[j]
, then we know that there are now count[i]
additional sequences to be counted of that length (ie. count[j] += count[i]
).
Complexity Analysis

Time Complexity: where is the length of
nums
. There are two forloops and the work inside is . 
Space Complexity: , the space used by
lengths
andcounts
.
Approach 2: Segment Tree
Intuition
Suppose we knew for each length L
, the number of sequences with length L
ending in x
. Then when considering the next element of nums
, updating our knowledge hinges on knowing the number of sequences with length L1
ending in y < x
. This type of query over an interval is a natural fit for using some sort of tree.
We could try using Fenwick trees, but we would have to store of them, which naively might be space. Here, we focus on an implementation of a Segment Tree.
Algorithm
Implementing Segment Trees is discussed in more detail here. In this approach, we will attempt a variant of segment tree that doesn't use lazy propagation.
First, let us call the "value" of an interval, the longest length of an increasing subsequence, and the number of such subsequences in that interval.
Each node knows about the interval of nums
values it is considering [node.range_left, node.range_right]
, and it knows about node.val
, which contains information on the value of interval. Nodes also have node.left
and node.right
children that represents the left and right half of the interval node
considers. These child nodes are created on demand as appropriate.
Now, query(node, key)
will tell us the value of the interval specified by node
, except we'll exclude anything above key
. When key is outside the interval specified by node
, we return the answer. Otherwise, we'll divide the interval into two and query both intervals, then merge
the result.
What does merge(v1, v2)
do? Suppose two nodes specify adjacent intervals, and have corresponding values v1 = node1.val, v2 = node2.val
. What should the aggregate value, v = merge(v1, v2)
be? If there are longer subsequences in one node, then v
will just be that. If both nodes have longest subsequences of equal length, then we should count subsequences in both nodes. Note that we did not have to consider cases where larger subsequences were made, since these were handled by insert
.
What does insert(node, key, val)
do? We repeatedly insert the key
into the correct half of the interval that node
specifies (possibly a point), and after such insertion this node's value could change, so we merge the values together again.
Finally, in our main algorithm, for each num in nums
we query
for the value length, count
of the interval below num
, and we know it will lead to count
additional sequences of length length + 1
. We then update our tree with that knowledge.
Complexity Analysis

Time Complexity: where is the length of
nums
. In our main for loop, we do work toquery
andinsert
. 
Space Complexity: , the space used by the segment tree.
Analysis written by: @awice. Approach 2 inspired by @dut200901102.