C++最長上昇サブシーケンス

2792 ワード

ダイナミックプランニングに基づく考え方

#include
#include
#include
#include
#include
#include
using namespace std;

int main() {
	int arr[] = { 2,1,4,3,1,5,6};
	int len[8];  //       ， arr[i]      ，         
	int max_val = 1;
	for (int i = 0; i < 8; i++) {
		len[i] = 1;//          ，                
		for (int j = 0; j < i; ++j) {  
			if (arr[j] < arr[i] && len[i] < len[j]+1)//                     
				len[i] = len[j] + 1;
		}
		max_val = max(max_val, len[i]);
	}
	cout<< max_val;

	return 0;
}

欲張り+二分検索に基づく

#include
#include
#include
#include
#include
#include
using namespace std;

int main() {
	vector arr{ 2,1,4,3,1,4,5,6 };
	vector len;  //       
	len.push_back(arr[0]);
	for (int i = 1; i < 8; ++i) {
		if (arr[i] > len.back())
			len.push_back(arr[i]);
		else if (arr[i] < len.back()) {
			int low = 0, high = len.size()-1;
			while (low <= high) {
				int mid = (low + high) / 2;
				if (len[mid] < arr[i]) {//          a[i]  
					low = mid + 1;
				}
				else if (len[mid] >= arr[i]) {
					high = mid - 1;
				}
			}
			len[low] = arr[i];
		}
	}
	for (auto temp : len)
		cout << temp << " ";
	return 0;
}

#include
#include
#include
#include
#include
#include
using namespace std;

int main() {
	vector A{ 2,1,4,3,1,4,5,6 };
	vector len;  //       
	len.push_back(A[0]);
	for (int i = 1; i < 8; ++i) {
		if (A[i] > len.back())
			len.push_back(A[i]);
		else if (A[i] < len.back()) {
			auto it = lower_bound(len.begin(), len.end(), A[i]);//          ，     >=A[i]   
			if (it != len.end())
				*it = A[i];				
		}
	}
	for (auto temp : len)
		cout << temp << " ";
}

非厳密増分サブシーケンス

#include
#include
#include
#include
#include
#include
using namespace std;

int main() {
	vector A{ 2,1,4,3,1,4,5,6 };
	vector len;  //       
	len.push_back(A[0]);
	for (int i = 1; i < 8; ++i) {
		if (A[i] > len.back())
			len.push_back(A[i]);
		else if (A[i] < len.back()) {
			auto it = upper_bound(len.begin(), len.end(), A[i]);//        ，     >A[i]  
			if (it != len.end())
				*it = A[i];				
		}
	}
	for (auto temp : len)
		cout << temp << " ";
}

c++templateの含むモデル

IE11 と reCAPTCHA と core-js を組み合わせると何かが壊れることがある