leetcode 300. Longest Increasing Subsequence

今天药忘吃喽~ 2022-07-28 01:20 158阅读 0赞

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?

class Solution {
    public:
    	int lengthOfLIS(vector<int>& nums) {
    		if (nums.size() < 2)
    			return nums.size();
    		vector<int>starter(nums.size());
    		int maxlen = 0;
    		for (int i = 0; i < nums.size() - maxlen; i++)
    		{
    			if (starter[i] == 0)
    			{
    				starter[i] = 1;
    				vector<int>candi;
    				candi.push_back(i);
    				int k = 1;
    				while (!candi.empty())
    				{
    					if (k>maxlen)
    						maxlen = k;
    					vector<int>newcandi;
    					for (int w = 0; w < candi.size(); w++)
    					{
    						for (int j = candi[w]+1; j < nums.size(); j++)
    						{
    							if (nums[j]>nums[candi[w]])
    							{
    								starter[j] = 1;
    								if (find(newcandi.begin(), newcandi.end(), j) == newcandi.end())
    								newcandi.push_back(j);
    								for (int h = j + 1; h < nums.size(); h++)
    								{
    									if (nums[h]>nums[candi[w]] && nums[h] < nums[j])
    									{
    										starter[h] = 1;
    										if (find(newcandi.begin(), newcandi.end(), h) == newcandi.end())
    										newcandi.push_back(h);
    									}
    								}
    								break;
    							}
    						}
    					}
    					k++;
    					candi = newcandi;
    				}
    			}
    		}
    		return maxlen;
    	}
    };

accepted