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 for-loops and the work inside is .

  • Space Complexity: , the space used by lengths and counts.


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 L-1 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 to query and insert.

  • Space Complexity: , the space used by the segment tree.


Analysis written by: @awice. Approach 2 inspired by @dut200901102.