LeetCode *** 300. Longest Increasing Subsequence

本文主要是介绍LeetCode *** 300. Longest Increasing Subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

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

分析：

我目前做的是n^2时间复杂度。有时间了想n*logn复杂度的做法吧。占坑。

代码：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int max=0,size=nums.size();for(int i=0;i<size;++i){int tmp=1,pre=nums[i],next=nums[i];for(int j=i-1;j>=0;--j){if(nums[j]<pre){tmp++;pre=nums[j];}}for(int j=i+1;j<size;++j){if(nums[j]>next){tmp++;next=nums[j];}}max=max>tmp?max:tmp;}return max;}
};

这篇关于LeetCode *** 300. Longest Increasing Subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---