【动态规划】「线性DP」子序列问题 LIS/LNDS/LDS/LNIS

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

1644104851041

LIS不严格并且可以不连续的最长上升的长度元素不可相等。
LNDS同 LIS区别在于 LNDS 元素可相等。

LIS

public static void main(String[] args) {
    int n = 8;
    int[] A = {0, 5, 6, 3, 6, 8, 7, 9, 5};
    int[] LIS = new int[n+1];
    Arrays.fill(LIS, 1);
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(A[i] > A[j]) LIS[i] = Math.max(LIS[i], LIS[j] + 1);
        }
    }
    for(int i = 1; i <= n; i++) System.out.print(LIS[i] + " ");
}

LNDS

public static void main(String[] args) {
    int n = 8;
    int[] A = {0, 5, 6, 3, 6, 8, 7, 9, 5};
    int[] LNDS = new int[n+1];
    Arrays.fill(LNDS, 1);
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(A[i] >= A[j]) LNDS[i] = Math.max(LNDS[i], LNDS[j] + 1);
        }
    }
    for(int i = 1; i <= n; i++) System.out.print(LNDS[i] + " ");
}

LDS

public static void main(String[] args) {
    int n = 8;
    int[] A = {0, 5, 6, 3, 6, 8, 7, 9, 5};
    int[] LDS = new int[n+1];
    Arrays.fill(LDS, 1);
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(A[i] < A[j]) LDS[i] = Math.max(LDS[i], LDS[j] + 1);
        }
    }
    for(int i = 1; i <= n; i++) System.out.print(LDS[i] + " ");
}

LNIS

public static void main(String[] args) {
    int n = 8;
    int[] A = {0, 5, 6, 3, 6, 8, 7, 9, 5};
    int[] LNIS = new int[n+1];
    Arrays.fill(LNIS, 1);
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(A[i] <= A[j]) LNIS[i] = Math.max(LNIS[i], LNIS[j] + 1);
        }
    }
    for(int i = 1; i <= n; i++) System.out.print(LNIS[i] + " ");
}