Проблема построения мостов - как применить самую длинную возрастающую подпоследовательность?

Вот реализация Java-задачи.

    package DP;

    import java.util.Arrays;
    import java.util.Comparator;

    public class BuildingBridges {

        public static void main(String[] args) {
            Pair[] A = new Pair[7];
            A[0] = new Pair(22,4);
            A[1] = new Pair(2,6);
            A[2] = new Pair(10,3);
            A[3] = new Pair(15,12);
            A[4] = new Pair(9,8);
            A[5] = new Pair(17,17);
            A[6] = new Pair(4,2);

            System.out.println(lis(A));
        }

        public static int lis(Pair[] A){
            Arrays.sort(A, new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.x - o2.x;
                }
            });

            int n = A.length;
            int max = 0;
            int[] dp = new int[n];
            Arrays.fill(dp, 1);

            for(int i=1; i<n; i++){
                for(int j=0; j<i; j++){
                    if(A[i].y > A[j].y){
                        dp[i] = Math.max(dp[i], dp[j]+1);
                    }
                }
                max = Math.max(max, dp[i]);
            }

            return max;
        }

        public static class Pair{
            int x, y;
            public Pair(int x_, int y_){
                x = x_;
                y = y_;
            }
        }

    }

Это проблема динамического программирования, которая может быть смоделирована даже как проблема самой длинной подпоследовательности. Рассмотрим координаты городов к северу от реки a1, a2, a3..aN. Теперь найдите соответствующие города на юге реки и отметьте их как a1, a2, a3..aN. Тогда решением проблемы будет самая длинная общая последовательность последовательностей, образованных алиами на севере и юге реки.

Сортировать один список и найти LIS в другом. Код C ++ ->

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(pair<int,int> a, pair<int,int> b){
    return a.first<b.first;
}

int bridges(vector<pair<int,int> > connect){
    int i, j, n=connect.size();
    sort(connect.begin(),connect.end(),cmp);
    vector<int> lis(n,1);
    int m=0;
    for(i=0;i<n;i++){
        for(j=i-1;j>=0;j--){
            if(connect[i].second>connect[i].first)lis[i]=max(lis[i],lis[j]+1);
        }
        m=max(m,lis[i]);
    }
    return m;
}

int main(){
    int n, i;
    cin >> n;
    vector<pair<int,int> > a(n);
    for(i=0;i<n;i++)cin >> a[i].first >> a[i].second;
    cout << bridges(a) <<endl;
    return 0;
}

Это рабочий код в c ++ для вышеуказанной проблемы.

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

struct pairs{
int x;
int y;  
};

bool myf(struct pairs p1,struct pairs p2){
return p1.x<p2.x;   
}

int lis(struct pairs a[],int n){
sort(a,a+n,myf);

int lis[n];

for(int i=0;i<n;i++)
    lis[i]=1;

for(int i=1;i<n;i++){

    for(int j=0;j<i;j++){
        if((a[j].y<a[i].y)&&(lis[i]<lis[j]+1))
            lis[i]=lis[j]+1;
    }
}

int max=lis[0];

for(int i=1;i<n;i++){
    if(max<lis[i])
        max=lis[i]; 
}

return max;
}

int main()
{
struct pairs arr[100];
int n;
cin>>n;
for(int i=0;i<n;i++){
    cin>>arr[i].x>>arr[i].y;    
}

int max=lis(arr,n);
cout<<max<<"\n";

return 0;
}