# Find maximum non contiguous subarray that respect a specific rule [closed]

Given these two arrays:

[5, 3, 4, 1, 2]

[1, 3, 2, 4, 5]


Find the maximum subsequence in both arrays that the index of the elements are in a crescent order:

Example: [3, 4] it's an answer because the indexes are in a crescent way in both arrays. (same as [1, 2]). Therefore, the subsequence the answer [3, 4, 1] is wrong, because the indexes are the crescent in the first array, but not on the second one.

The output of the program should be the length of the max non-contiguous subarray.

This is the code I wrote for solving this, but it only takes the first subarray, and I'm having difficulty to generate the other possibilities

vector<pair<int, double>> esq;
vector<pair<int, double>> dir;
// N is the size of esq and dir
// pair<int, double> where int is the key (show in the example array) and double is the value, used for sort previously.
int cont = 1;
for (int i = 0; i < N - 1; i++)
{
int cont_aux = 1;
pair<int, double> pivot = esq[i];
auto it_dir = find_if(dir.begin(), dir.end(), [&pivot](const pair<int, double> &p) { return p.first == pivot.first; });
int last_index = it_dir - dir.begin();

for (int j = 0; j < N; j++)
{
pair<int, double> actual = esq[j];
auto it = find_if(dir.begin(), dir.end(), [&actual](const pair<int, double> &p) { return p.first == actual.first; });
int pos = it - dir.begin();

if (pos >= last_index) {
last_index = pos;
cont_aux++;
}
}

cont = max(cont, cont_aux);
}

cout << cont << endl;

• Can you define this "crescent order" ? How is your problem different from LCS?en.wikipedia.org/wiki/Longest_common_subsequence_problem – JimN Dec 8 '17 at 19:11
• That is exacly what I'm looking for. Thank you! – Emanuel Huber Dec 8 '17 at 19:14
• What's a "crescent order"? What kind of an answer are you looking for? Code-based questions are off-topic, here, so we won't write the rest of hte code for you. Also, many people here won't understand C++. – David Richerby Dec 8 '17 at 19:46
• I don't see a question here. This is a question-and-answer site, so we require you to articulate a specific question in your post. – D.W. Dec 9 '17 at 6:04