# 300. Longest Increasing Subsequence 最长递增子序列

@TOC

## # 题目描述

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

Example:

``````Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
``````

Note:

1. There may be more than one LIS combination, it is only necessary for you to return the length.
2. Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

## # 解题方法

Python代码：

``````class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
dp = [0] * len(nums)
dp[0] = 1
for i in range(1, len(nums)):
tmax = 1
for j in range(0, i):
if nums[i] > nums[j]:
tmax = max(tmax, dp[j] + 1)
dp[i] = tmax
return max(dp)
``````

C++代码如下：

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
const int N = nums.size();
if (N == 0) return 0;
// dp[i] means the LIS when the subsequence ends with nums[i]
vector<int> dp(N, 1);
for (int i = 1; i < N; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
``````

## # 日期

2018 年 4 月 4 日 —— 清明时节雪纷纷～～下雪了，惊不惊喜，意不意外？ 2019 年 1 月 7 日 —— 新的一周开始啦啦啊