# 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;


## closed as unclear what you're asking by David Richerby, fade2black, Evil, Rick Decker, JuhoDec 15 '17 at 15:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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