# 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

## 1 Answer

I will move my comment to an answer, since you seemed to indicate that the comment solved your problem.

Your problem is normally called the Longest Common Subsequence problem. It does not require the common subsequence to be contiguous. It can be solved efficiently with dynamic programming, and it is an early example of dynamic programming in many textbooks.

There are many implementations of LCS available online. The wiki article on LCS I linked to in the above comment is a good place to start.