# \[300]\[中等]\[贪心]\[二分]\[动态规划]\[树状数组] 最长上升子序列

## 题目描述

[300. 最长上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

```
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
```

说明:

* 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
* 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

## 解题思路

### 动态规划

定义`dp[i]`是前`i`个元素中, 以第`i`个元素为结尾的最长上升子序列的长度, 即`nums[i]`必须被选取.

要求新位置的状态值, 就需要遍历这个位置之前所有的`dp[i]`, 看上升子序列能否拼接上当前的数字, 因此状态转移方程为:

$$dp\[i] = \text{max}(dp\[j]) + 1, \text{其中} , 0 \leq j < i , \text{且} , \textit{num}\[j]<\textit{num}\[i]$$

最后遍历整个`dp`, 找到最大值.

```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        dp = [1]
        for i in range(1, n):
            max_seq = 1
            for j in range(i):
                if nums[i] > nums[j]:
                    max_seq = max(max_seq, dp[j] + 1)
            dp.append(max_seq)
        return max(dp)
```

### 贪心 + 二分

[一步一步推导出官方最优解法，详细图解](https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/yi-bu-yi-bu-tui-dao-chu-guan-fang-zui-you-jie-fa-x/)

```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        mins = []
        for num in nums:
            index = bisect.bisect_left(mins, num)
            if index == len(mins):
                mins.append(num)
            else:
                mins[index] = num
        return len(mins)
```

### 树状数组

首先将原数组`nums`去重排序, 得到树状数组`C`的长度和每个位置对应的数值. 树状数组中记录的值为以**当前区间**内的任一数字结尾的最长子序列的长度, 因此更新需要使用`max`, 而不是加和.

从左到右遍历数组, 对于数值`num`, 找到其在树状数组中的位置`index`. 首先我们遍历这个位置之前所有区间的树状数组的值, 因为`num`可以拼接到其之前的任意一个数之后, 组成上升序列. 找到其中的最大值, 再加上`num`本身的长度`1`, 就是`num`这个数在原数组对应位置的最大上升序列长度了, 记为`current_max`.

找到这个结果之后, 要更新树状数组, 其父节点所代表的区间, 对应的树状数组的值, 也要判断下是否要更新. 一路向上更新即可.

```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        A = list(set(nums))
        A.sort()
        A = [0] + A
        mapping = {num: i for i, num in enumerate(A)}
        C = [0] * len(A)

        final_max = 0
        for num in nums:
            index = mapping[num] - 1  # 严格递增, 从第一个小于此数的位置找起
            current_max = 0
            while index > 0:
                current_max = max(current_max, C[index])
                index -= index & (-index)
            final_max = max(final_max, current_max + 1)

            # 修改
            index = mapping[num]
            while index < len(A):
                C[index] = max(C[index], current_max + 1)
                index += index & (-index)

        return final_max
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/shu-zu/300-zui-chang-shang-sheng-zi-xu-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.