find longest increasing subsequence

Hi,

ich moechte die laengste increasing subsequence in einem array finden. Eine Increasing Subsequence ist eine Sequenz in der die Zahlen strikt groesser werden.

mit dynamic programming liegt die laufzeitkomplexiteat des algos bei O(n^2)...kann man/wie kann man den algo noch schneller machen?

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> find_long_inc_subseq(vector<int> &seq) {
	unordered_map<int, vector<int>> ht;

	for(int i = 0; i < seq.size(); i++) {
		vector<int> subseq;

		if(i > 0) {
			int max_index = 0;
			int max_size = 0;
			int index_start = i - 1;
			bool smaller_sub_seq_found = false;

			for(int j = 0; j < ht.size(); j++) {
				auto it = ht.find(index_start);

				if(it->second.back() < seq[i] && it->second.size() > max_size) {
					smaller_sub_seq_found = true;
					max_size = it->second.size();
					max_index = index_start;
				}

				index_start--;
			}

			if(smaller_sub_seq_found) {
				auto it = ht.find(max_index);

				for(auto it2 = it->second.begin(); it2 != it->second.end(); it2++) {
					subseq.push_back(*it2);
				}
			}
		}

		subseq.push_back(seq[i]);
		ht.insert(make_pair(i, subseq));
	}

	return ht.find(seq.size()-1)->second;
}

int main() {
	// your code goes here

	vector<int> seq =  {10, 22, 9, 33, 21, 50, 41, 60, 80};
	vector<int> long_sub_seq = find_long_inc_subseq(seq);

	for_each(long_sub_seq.begin(), long_sub_seq.end(), [](int val) { cout << val << ' '; });
	cout << '\n';

	return 0;
}

Meep Meep

das wäre in deinem beispiel 41-60-80 ?

Meep Meep

Meep Meep schrieb:

das wäre in deinem beispiel 41-60-80 ?

Der Code spuckt folgendes Ergebnis aus:
10 22 33 41 60 80

Das ist aber nicht eindeutig. Könnte genauso gut das hier liefern:
10 22 33 50 60 80

Meep: Nee, die Elemente müssen nicht angrenzend in der Sequenz sein.
OP: Warum googlest Du nicht einfach? Mannmannmann...

habe ein problem behoben:

vector<int> find_long_inc_subseq(vector<int> &seq) {
	unordered_map<int, vector<int>> ht;

	for(int i = 0; i < seq.size(); i++) {
		vector<int> subseq;

		if(i > 0) {
			int max_index = 0;
			int max_size = 0;
			int index_start = i - 1;
			bool smaller_sub_seq_found = false;

			for(int j = 0; j < ht.size(); j++) {
				auto it = ht.find(index_start);

				if(it->second.back() < seq[i] && it->second.size() > max_size) {
					smaller_sub_seq_found = true;
					max_size = it->second.size();
					max_index = index_start;
				}

				index_start--;
			}

			if(smaller_sub_seq_found) {
				auto it = ht.find(max_index);

				for(auto it2 = it->second.begin(); it2 != it->second.end(); it2++) {
					subseq.push_back(*it2);
				}
			}
		}

		subseq.push_back(seq[i]);
		ht.insert(make_pair(i, subseq));
	}

	return ht.find(seq.size()-1)->second;
}

mein algo gibt nur eine longest increasing subsequence aus...
10 22 33 50 60 80...waere auch ein gueltiges ergebnis

sorry, habe vergessen den ganzen code zu kopieren:

vector<int> find_long_inc_subseq(vector<int> &seq) {
	unordered_map<int, vector<int>> ht;

	for(int i = 0; i < seq.size(); i++) {
		vector<int> subseq;

		if(i > 0) {
			int max_index = 0;
			int max_size = 0;
			int index_start = i - 1;
			bool smaller_sub_seq_found = false;

			for(int j = 0; j < ht.size(); j++) {
				auto it = ht.find(index_start);

				if(it->second.back() < seq[i] && it->second.size() > max_size) {
					smaller_sub_seq_found = true;
					max_size = it->second.size();
					max_index = index_start;
				}

				index_start--;
			}

			if(smaller_sub_seq_found) {
				auto it = ht.find(max_index);
				for(auto it2 = it->second.begin(); it2 != it->second.end(); it2++) {
					subseq.push_back(*it2);
				}
			}
		}

		subseq.push_back(seq[i]);
		ht.insert(make_pair(i, subseq));
	}

	int max_index = 0;
	int max_size = 0;
	for(int i = 0; i < ht.size(); i++) {
		auto it = ht.find(i);

		if(it->second.size() > max_size) {
			max_size = it->second.size();
			max_index = i;
		}
	}
	return ht.find(max_index)->second;
}