欲張りアルゴリズム——最長上昇サブシーケンス

タイトルの説明:
整数配列を与え,この配列の最長厳格な増分サブシーケンスの長さを求める.例えば、シーケンス1 2 2 4 3の最長厳格増分サブシーケンスは、1,2,4または1,2,3である.彼らの長さは3です.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースについて、入力される第1の動作の整数n(1<=n<=10000000):入力するシーケンスの長さを表す第2の行には、この配列の数値を表すn個の整数が含まれる.整数はintの範囲内です.
出力:
各テストケースについて、最長厳格なサブシーケンス長を出力します.
サンプル入力:

4
4 2 1 3
5
1 1 1 1 1

サンプル出力:

2
1

この問題は貪欲なアルゴリズムで行い、構想は以下の通りである.
1、欲張り選択の性質とは、求める問題の全体的な最適解が一連の局所的な最適選択、すなわち欲張り選択によって達成できることを意味する.これは貪欲アルゴリズムが実行可能な最初の基本要素であり、貪欲アルゴリズムと動的計画アルゴリズムの主な違いでもある.
2、この問題では、最後の上昇サブシーケンスを格納するために配列を定義し、まず最初の数を配列に格納し、その後の数については、最初の数と比較し、最初の数より大きい場合は格納し、そうでない場合は、二分法を使用して配列の最初の数を検索し、置き換えます.
3、この方法により、配列中の配列が秩序化され、相対的に小さい配列であることを保証することができ、すなわち、最も長男の配列になる可能性がより大きい.
具体的なc++コードは以下の通りです.
#include #include using namespace std; int maxLongNoDrop(const vector&a)/最長上昇サブシーケンス{vectors;int l=a.size();if(l==0){return 0;}s.push_back(a[0]);int i = 1;for (i = 1; i{if (a[i]>s.back()){s.push_back(a[i]);}else{int leftn = 0, rightn = s.size() - 1, mid = 0;while (leftn <=rightn){mid = (rightn + leftn)/2;if (a[i] > s[mid]){leftn = mid + 1; }else{rightn = mid - 1;}}s[leftn] = a[i];}}return s.size(); } int main() {vector vin = { 1, 3, 6, 5, 8, 0, 3 };int maxlong = maxLongNoDrop(vin);cout << maxlong << endl;system("pause");return 0; }