本文主要是介绍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(n2) 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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!