# Longest Increasing Subsequence

<https://leetcode.com/problems/longest-increasing-subsequence/description/>

> Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

## Thoughts

看到数组求某性质的值想DP。如果让f\[i]\[j]表示以从i到j的substring最长升序则无法知道当前nums\[i]是否能和已有子序列拼接。所以必须要存下能与当前nums\[i]作比较的最后元素。因此想到f\[i]为以nums\[i]为尾组成的序列的LIS。

<https://www.zhihu.com/question/23995189>

> 给定一个数列，长度为N，
>
> 设F\_{k}为：以数列中第k项结尾的最长递增子序列的长度.
>
> 求F\_{1}..F\_{N} 中的最大值.
>
> 设A为题中数列，状态转移方程为：
>
> > ![F\_{1} = 1](https://www.zhihu.com/equation?tex=F_{1}+%3D+1) （根据状态定义导出边界情况） ![F\_{k}=max(F\_{i}+1 | A\_{k}\&gt;A\_{i}, i\in (1..k-1)) ](https://www.zhihu.com/equation?tex=F_{k}%3Dmax\(F_{i}%2B1+|+A_{k}%3EA_{i}%2C+i\in+\(1..k-1\)\)+) ![(k\&gt;1)](https://www.zhihu.com/equation?tex=\(k%3E1\))

## Code

```
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            max = Math.max(max, f[i]);
        }

        return max;
    }
}
```

## Analysis

做题耗时21min。

Errors:

1. 结果直接返回了f\[n-1].

TC: O(n^2).

此题还有O(nlgn)解法, 参见二分法章节。