Longest Increasing Subsequence最長上昇サブシーケンス

無秩序な整数配列を指定し、最長上昇サブシーケンスの長さを見つけます.
例:

  : [10,9,2,5,3,7,101,18]
  : 4 
  :           [2,3,7,101]，      4。

説明:

には、最長上昇サブシーケンスの組み合わせが複数ある可能性があります.対応する長さを出力するだけでいいです.

あなたのアルゴリズムの時間複雑度はO(n 2)であるべきです.

ステップアップ:アルゴリズムの時間的複雑さをO(n log n)に下げることができますか?
考え方:
この問題は博文の構想を参考にした.
https://www.cnblogs.com/grandyang/p/4938187.html
時間の複雑さO(nlogn)は、自分では考えられなかったし、複雑すぎる感じがします.具体的な考え方は以下の通りです.
増分配列dpを維持し、現在の要素がdpの最初の要素より小さい場合は最初の要素を置き換え(最初の要素を上書き)、最後の要素より大きい場合はdpの最後(最後の要素を上書きしない)、サイズが最初の要素と最後の要素にある場合は、二分法により最初の要素より大きい位置を見つけます.元の要素(上書き)を置き換えます.
コードは次のとおりです.

    int lengthOfLIS(vector& nums) {
	vector dp;
	if (nums.size() <= 0) {
		return 0;
	}
	dp.push_back(nums[0]);
	for (int i = 1; i < nums.size(); i++) {
		if (nums[i] < dp[0]) {
			dp[0] = nums[i];
			continue;
		}
		if (nums[i] > dp[dp.size() - 1]) {
			dp.push_back(nums[i]);
			continue;
		}
		int left = 0;
		int right = dp.size()-1;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (dp[mid] < nums[i]) {
				left = mid + 1;
			}
			else {
				right = mid;
			}
		}
		dp[right] = nums[i];
		     
    }
        return dp.size();  
    }

考え方2:dpを用いて、1次元配列dpを維持することによって、dp[i]はi番目の要素の最長男シーケンスの個数を表し、dp[i+1]の値は[0,j]を遍歴する要素(0<=j<=i)に等しく、対応するnums[j]

dp[i] = max(dp[j] + 1, dp[i]);

jを巡回してもnums[j]を満たす要素がない場合
参照コード:

    int lengthOfLIS(vector& nums) {
        if(nums.size()==0){
            return 0;
        }
	int *dp = new int[nums.size()];
	int res = 1;
	for (int i = 1; i < nums.size(); i++) {
		dp[i] = INT_MIN;
	}
	dp[0] = 1;
	for (int i = 1; i < nums.size(); i++) {
		for (int j = 0; j <= i; j++) {
			if (nums[j] < nums[i]) {
				dp[i] = max(dp[j] + 1, dp[i]);
				res = max(res, dp[i]);
			}
		}
        dp[i]=dp[i]==INT_MIN?1:dp[i];
	}

	delete[] dp;
	return res;        
    }

構想3:この問題はまた二分検索+動的計画で行い、1次元の配列(空に初期化)resを宣言することができ、resは下付きiまでの時点で、現在保存されている可能性のある最長の増分サブシーケンスを表し、resの中で必ずしも増分されたサブシーケンスではないことに注意するが、resのsizeは現在の最適な増分サブシーケンスの長さである.
例は次のとおりです.
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

A[0] = 0. Case 1. There are no active lists, create one.
0.
-----------------------------------------------------------------------------
A[1] = 8. Case 2. Clone and extend.
0.
0, 8.
-----------------------------------------------------------------------------
A[2] = 4. Case 3. Clone, extend and discard.
0.
0, 4.
0, 8. Discarded
-----------------------------------------------------------------------------
A[3] = 12. Case 2. Clone and extend.
0.
0, 4.
0, 4, 12.
-----------------------------------------------------------------------------
A[4] = 2. Case 3. Clone, extend and discard.
0.
0, 2.
0, 4. Discarded.
0, 4, 12.
-----------------------------------------------------------------------------
A[5] = 10. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 10.
0, 4, 12. Discarded.
-----------------------------------------------------------------------------
A[6] = 6. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 6.
0, 2, 10. Discarded.
-----------------------------------------------------------------------------
A[7] = 14. Case 2. Clone and extend.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
-----------------------------------------------------------------------------
A[8] = 1. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2. Discarded.
0, 2, 6.
0, 2, 6, 14.
-----------------------------------------------------------------------------
A[9] = 9. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Discarded.
-----------------------------------------------------------------------------
A[10] = 5. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 5.
0, 2, 6. Discarded.
0, 2, 6, 9.
-----------------------------------------------------------------------------
A[11] = 13. Case 2. Clone and extend.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-----------------------------------------------------------------------------
A[12] = 3. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 5. Discarded.
0, 2, 6, 9.
0, 2, 6, 9, 13.
-----------------------------------------------------------------------------
A[13] = 11. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Discarded.
-----------------------------------------------------------------------------
A[14] = 7. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9. Discarded.
0, 2, 6, 9, 11.
----------------------------------------------------------------------------
A[15] = 15. Case 2. Clone and extend.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. 
----------------------------------------------------------------------------

図に示すように、私たちは毎回複数のキューを維持し、各キューは秩序化されていますが、実際には複雑にする必要はありません.私たちは1つのキューresを維持するだけでいいです.元の配列numsを1回遍歴し、現在の値n=nums[i]を取り出すたびに、resの中でn以上の最初の下付き文字を判断し、下付き文字に対応する要素を上書きし、見つからない場合、すべてのresの要素よりも大きいことを証明すると、resの末尾にn要素を加え、最後にres.size()を返す.
参照コード(時間複雑度nlogn):
 

class Solution {
public:
int lengthOfLIS(vector& nums) {
	vector res;
	for (int &n : nums) {
		auto it = lower_bound(res.begin(), res.end(), n);
		if (it == res.end()) res.push_back(n);
		else *it = n;
	}
	return res.size();
}
};