Code

Python

def getLargestIndexLen(feature1, feature2):
    pairs = zip(feature1, feature2)
    f1, f2 = zip(*sorted(pairs))
    dp = [1] * len(feature2)
    for i in range(len(feature2)):
        for j in range(i):
            if f2[j] < f2[i] and f1[j] < f1[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

C++

#include <iostream>#include <vector>#include <algorithm>using namespace std;// Function to perform binary search and return the position where the element should be placedint binarySearch(vector<int>& lis, int target) {    int left = 0, right = lis.size() - 1;    while (left <= right) {        int mid = left + (right - left) / 2;        if (lis[mid] == target) {            return mid;        } else if (lis[mid] < target) {            left = mid + 1;        } else {            right = mid - 1;        }    }    // `left` will be the correct position where the target should be inserted    return left;}int getLargestIndexLen(vector<int>& feature1, vector<int>& feature2) {    vector<pair<int, int>> pairs;    // Step 1: Create pairs of (feature1, feature2)    for (int i = 0; i < feature1.size(); ++i) {        pairs.push_back({feature1[i], feature2[i]});    }    // Step 2: Sort by feature1    sort(pairs.begin(), pairs.end());    // Step 3: Extract the sorted feature2 values    vector<int> f2;    for (const auto& p : pairs) {        f2.push_back(p.second);    }    // Step 4: Implement LIS on f2 using binary search    vector<int> lis;    for (int num : f2) {        // Find the position where num should go in the lis array        int pos = binarySearch(lis, num);        if (pos < lis.size()) {            // If the position is within lis, we replace the element            lis[pos] = num;        } else {            // If the position is at the end of lis, we extend lis            lis.push_back(num);        }    }    // The size of the lis array is the length of the longest increasing subsequence    return lis.size();}

Comments

1. Condition in the problem reduces to the statement that any 2 elements we select should have same relative order for features 1 and 2.
2. If we combine the two feature arrays into a (feature1, feature2) pair array, we can rearrange the elements however we want
3. So let us sort this pair by feature1
4. Then if we select some indices, we want to make sure that feature1 is distinct for them and feature2 is increasing
5. If we break ties during sorting by decreasing order of feature2, then selecting a strictly increasing subsequence of feature2 ensures that selected feature1 values are also strictly increasing
6. Thus we have the full solution: Sort (feature1, feature2) pairs in increasing order of feature1, breaking ties in decreasing order of feature2. The best we can do is select the longest strictly increasing subsequence of feature2 in the sorted pair array.