## 673. Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

```Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
```

Example 2:

```Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
```

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

b'
\n\n

#### Approach #1: Dynamic Programming [Accepted]

\n

Intuition and Algorithm

\n

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.

\n

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`.

\n

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]`).

\n
`class Solution(object):\n    def findNumberOfLIS(self, nums):\n        N = len(nums)\n        if N <= 1: return N\n        lengths =  * N #lengths[i] = longest ending in nums[i]\n        counts =  * N #count[i] = number of longest ending in nums[i]\n\n        for j, num in enumerate(nums):\n            for i in xrange(j):\n                if nums[i] < nums[j]:\n                    if lengths[i] >= lengths[j]:\n                        lengths[j] = 1 + lengths[i]\n                        counts[j] = counts[i]\n                    elif lengths[i] + 1 == lengths[j]:\n                        counts[j] += counts[i]\n\n        longest = max(lengths)\n        return sum(c for i, c in enumerate(counts) if lengths[i] == longest)\n`
\n

Java

\n
`class Solution {\n    public int findNumberOfLIS(int[] nums) {\n        int N = nums.length;\n        if (N <= 1) return N;\n        int[] lengths = new int[N]; //lengths[i] = length of longest ending in nums[i]\n        int[] counts = new int[N]; //count[i] = number of longest ending in nums[i]\n        Arrays.fill(counts, 1);\n\n        for (int j = 0; j < N; ++j) {\n            for (int i = 0; i < j; ++i) if (nums[i] < nums[j]) {\n                if (lengths[i] >= lengths[j]) {\n                    lengths[j] = lengths[i] + 1;\n                    counts[j] = counts[i];\n                } else if (lengths[i] + 1 == lengths[j]) {\n                    counts[j] += counts[i];\n                }\n            }\n        }\n\n        int longest = 0, ans = 0;\n        for (int length: lengths) {\n            longest = Math.max(longest, length);\n        }\n        for (int i = 0; i < N; ++i) {\n            if (lengths[i] == longest) {\n                ans += counts[i];\n            }\n        }\n        return ans;\n    }\n}\n`
\n

Complexity Analysis

\n
\n
• \n

Time Complexity: where is the length of `nums`. There are two for-loops and the work inside is .

\n
• \n
• \n

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

\n
• \n
\n
\n

#### Approach #2: Segment Tree [Accepted]

\n

Intuition

\n

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.

\n

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.

\n

Algorithm

\n

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.

\n

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.

\n

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.

\n

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.

\n

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`.

\n

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.

\n

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.

\n

Java

\n
`class Solution {\n    public Value merge(Value v1, Value v2) {\n        if (v1.length == v2.length) {\n            if (v1.length == 0) return new Value(0, 1);\n            return new Value(v1.length, v1.count + v2.count);\n        }\n        return v1.length > v2.length ? v1 : v2;\n    }\n\n    public void insert(Node node, int key, Value val) {\n        if (node.range_left == node.range_right) {\n            node.val = merge(val, node.val);\n            return;\n        } else if (key <= node.getRangeMid()) {\n            insert(node.getLeft(), key, val);\n        } else {\n            insert(node.getRight(), key, val);\n        }\n        node.val = merge(node.getLeft().val, node.getRight().val);\n    }\n\n    public Value query(Node node, int key) {\n        if (node.range_right <= key) return node.val;\n        else if (node.range_left > key) return new Value(0, 1);\n        else return merge(query(node.getLeft(), key), query(node.getRight(), key));\n    }\n\n    public int findNumberOfLIS(int[] nums) {\n        if (nums.length == 0) return 0;\n        int min = nums, max = nums;\n        for (int num: nums) {\n            min = Math.min(min, num);\n            max = Math.max(max, num);\n        }\n        Node root = new Node(min, max);\n        for (int num: nums) {\n            Value v = query(root, num-1);\n            insert(root, num, new Value(v.length + 1, v.count));\n        }\n        return root.val.count;\n    }\n}\n\nclass Node {\n    int range_left, range_right;\n    Node left, right;\n    Value val;\n    public Node(int start, int end) {\n        range_left = start;\n        range_right = end;\n        left = null;\n        right = null;\n        val = new Value(0, 1);\n    }\n    public int getRangeMid() {\n        return range_left + (range_right - range_left) / 2;\n    }\n    public Node getLeft() {\n        if (left == null) left = new Node(range_left, getRangeMid());\n        return left;\n    }\n    public Node getRight() {\n        if (right == null) right = new Node(getRangeMid() + 1, range_right);\n        return right;\n    }\n}\n\nclass Value {\n    int length;\n    int count;\n    public Value(int len, int ct) {\n        length = len;\n        count = ct;\n    }\n}\n`
\n

Python

\n
`class Node(object):\n    def __init__(self, start, end):\n        self.range_left, self.range_right = start, end\n        self._left = self._right = None\n        self.val = 0, 1 #length, count\n    @property\n    def range_mid(self):\n        return (self.range_left + self.range_right) / 2\n    @property\n    def left(self):\n        self._left = self._left or Node(self.range_left, self.range_mid)\n        return self._left\n    @property\n    def right(self):\n        self._right = self._right or Node(self.range_mid + 1, self.range_right)\n        return self._right\n\ndef merge(v1, v2):\n    if v1 == v2:\n        if v1 == 0: return (0, 1)\n        return v1, v1 + v2\n    return max(v1, v2)\n\ndef insert(node, key, val):\n    if node.range_left == node.range_right:\n        node.val = merge(val, node.val)\n        return\n    if key <= node.range_mid:\n        insert(node.left, key, val)\n    else:\n        insert(node.right, key, val)\n    node.val = merge(node.left.val, node.right.val)\n\ndef query(node, key):\n    if node.range_right <= key:\n        return node.val\n    elif node.range_left > key:\n        return 0, 1\n    else:\n        return merge(query(node.left, key), query(node.right, key))\n\nclass Solution(object):\n    def findNumberOfLIS(self, nums):\n        if not nums: return 0\n        root = Node(min(nums), max(nums))\n        for num in nums:\n            length, count = query(root, num-1)\n            insert(root, num, (length+1, count))\n        return root.val\n`
\n

Complexity Analysis

\n
\n
• \n

Time Complexity: where is the length of `nums`. In our main for loop, we do `\$\$O(\\log{N})\$\$` work to `query` and `insert`.

\n
• \n
• \n

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

\n
• \n
\n
\n

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

\n
'