java - (LIS) 最长递增子序列算法

Question

编辑
最后发现这种“Brute force”的方法是不对的。
所以我又写了两个方法来解决LIS问题。

• 对原始数组和排序后的数组使用 LCS。时间复杂度 = (n^2)。
• 使用 DP + 二进制搜索。时间复杂度 = O(nlgn)。

[代码在最后。]

---

我尝试使用蛮力查找最长递增子序列 (LIS)。但是我个人认为这个算法的时间复杂度是O(n ²)，等于DP方式，对吗？

// Find LIS Brute force.
public static int[] findLIS_BF (int[] givenArray) {
    int size = givenArray.length;
    int maxLen = Integer.MIN_VALUE;
    int prevIndex = 0;
    int tempLen = 1;
    int head = 0;
    for (int tempHead = 0; tempHead < size; tempHead ++) {
        prevIndex = tempHead;
        tempLen = 1;
        for (int subPointer = tempHead + 1; subPointer < size; subPointer ++) {
            if (givenArray[prevIndex] <= givenArray[subPointer]) {
                prevIndex = subPointer;
                tempLen ++;
            }
        }
        if (tempLen > maxLen) {
            maxLen = tempLen;
            head = tempHead;
        }
    }

    System.out.println("LIS by BF, max len = " + maxLen);
    int[] rest = new int[maxLen];
    int restIndex = 0;
    rest[restIndex] = givenArray[head];
    restIndex ++;
    prevIndex = head;
    for (int i = head + 1; i < size; i ++) {
        if (givenArray[prevIndex] <= givenArray[i]) {
            rest[restIndex] = givenArray[i];
            restIndex ++;
            prevIndex = i;
        }
    }
    return rest;
}

---

[编辑]
[LCS方法]

public class FindLIS_LCS {

// Find LIS by LCS.
// Time complexity = O(n^2).
// LCS.
// Time complexity = O(n^2).
// Note:
// UP LEFT MARK = -1.
// UP MARK = -2.
// LEFT MARK = -3.
private static int LCS (int[] firstA, int[] secondA, int[][]c, int[][]b) {
    int lenFA = firstA.length;
    int lenSA = secondA.length;

    // Init c matrix.
    for (int i = 0; i < lenFA; i ++) c[i][0] = 0;
    for (int i = 0; i < lenSA; i ++) c[0][i] = 0;

    for (int i = 1; i < lenFA+1; i ++) {
        for (int j = 1; j < lenSA+1; j ++) {
            if (firstA[i - 1] == secondA[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i - 1][j - 1] = -1;
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i - 1][j - 1] = -2;
            } else {
                c[i][j] = c[i][j - 1];
                b[i - 1][j - 1] = -3;
            }
        }
    }
    return c[lenFA][lenSA];
}

// Print out the LCS.
// Time complexity = O(m + n).
private static void printLCS_Helper (int[] firstA, int[][]b, int i, int j) {
    if (i < 0 || j < 0) return; // Base case.
    if (b[i][j] == -1) {
        printLCS_Helper(firstA, b, i - 1, j - 1);
        System.out.print(String.format("%-6d", firstA[i]));
    } else if (b[i][j] == -2) printLCS_Helper(firstA, b, i - 1, j);
    else printLCS_Helper(firstA, b, i, j - 1);
}
public static void printLCS (int[] firstA, int[][]b) {
    int size = firstA.length;
    printLCS_Helper(firstA, b, size - 1, size - 1);
}

// Quick sort for array.
// Time complexity = O(nlgn).
private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
    int temp = givenArray[firstIndex];
    givenArray[firstIndex] = givenArray[secondIndex];
    givenArray[secondIndex] = temp;
}
private static int partition (int[] givenArray, int start, int end, int pivotIndex) {
    int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left <= right) {
        while (givenArray[left] < pivot) left ++;
        while (givenArray[right] > pivot) right --;
        if (left <= right) {
            exchange(givenArray, left, right);
            left ++;
            right --;
        }
    }
    return left;
}
private static void quickSortFromMinToMax_Helper (int[] givenArray, int start, int end) {
    if (start >= end) return; // Base case.
    // Generate a random num in the range[start, end] as the pivot index to partition the array.
    int rand = start + (int) (Math.random() * ((end - start) + 1));
    int split = partition (givenArray, start, end, rand);
    // Do recursion.
    quickSortFromMinToMax_Helper(givenArray, start, split - 1);
    quickSortFromMinToMax_Helper(givenArray, split, end);
}
public static void quickSortFromMinToMax (int[] givenArray) {
    int size = givenArray.length;
    quickSortFromMinToMax_Helper(givenArray, 0, size - 1);
}

// Copy array.
public static int[] copyArray (int [] givenArray) {
    int size = givenArray.length;
    int[] newArr = new int[size];
    for (int i = 0; i < size; i ++) 
        newArr[i] = givenArray[i];
    return newArr;
}

// Main method to test.
public static void main (String[] args) {
    // Test data: {1, 2, 1, 4, 5, 3, 10}.
    //int[] givenArray = {1, 2, 1, 4, 5, 3, 10};
    int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};
    int size = givenArray.length;
    // Test finding LIS by LCS approach.
    int[] sortedArr = copyArray(givenArray);
    quickSortFromMinToMax (sortedArr);
    int[][]c = new int[size + 1][size + 1];
    int[][]b = new int[size][size];
    System.out.println("Test max len = " + LCS(givenArray, sortedArr, c, b));
    printLCS(givenArray, b);
}
}

[DP+二分查找法]

public class FindLIS {

// Linear search.
public static int linearSearch (int[] givenArray, int key) {
    int size = givenArray.length;
    for (int i = size - 1; i >= 0; i --) {
        if (givenArray[i] >= 0) 
            if (givenArray[i] < key) return i;
    }
    return -1;
}

// Find the len of the LIS.(Longest increasing (non-necessarily-adjacent) subsequence).
// DP + Binary search.
// Time complexity = O(nlgn).
// Note:
// This binary search to find the elem's index of the given array, which is less than the elem's value = key.
private static int biSearch (int[] givenArray, int start, int end, int key) {
    if (start > end) return -1;
    int mid = (start + end) / 2;
    if (givenArray[mid] <= key) return mid;
    else return biSearch(givenArray, start, mid - 1, key);
}

public static int findLISLen (int[] givenArray) {
    int size = givenArray.length;
    int maxLen = 1;
    int[] memo = new int[size];
    for (int i = 0; i < size; i ++) memo[i] = -10;
    memo[0] = givenArray[0];

    for (int i = 1; i < size; i ++) {
        if (givenArray[i] > memo[maxLen - 1]) {
            memo[maxLen] = givenArray[i];
            maxLen ++;
        } else {
            // int pos = linearSearch(memo, givenArray[i]); // Using linear search, the time complexity = O(n^2).
            int pos = biSearch(memo, 0, maxLen - 1, givenArray[i]); // Using Binary search, the time complexity = O(nlgn).
            memo[pos + 1] = givenArray[i];
        }
    }
    // Show memo.
    showArray(memo);
    return maxLen;
}


// Show array.
public static void showArray (int[] givenArray) {
    int size = givenArray.length;
    for (int i = 0; i < size; i ++) 
        System.out.print(String.format("%-6d", givenArray[i]));
    System.out.println();
}

// Main method to test.
public static void main (String[] args) {
    // Test data: {2, 1, 6, 3, 5, 4, 8, 7, 9}.
    //int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};
    //int[] givenArray = {1, 2, 1, 4, 5, 3, 10};
    int[] givenArray = {2, 1, 6, 3, 5, 4, 8, 7, 9};

    // Test finding the LIS by DP + Binary search.
    System.out.println("Test finding the LIS by DP + Binary search, max len = " + findLISLen(givenArray));

}
}

Answer 1

是的，您的方法和两种 DP 方法的复杂度都是 O(n^2)。对于 O(nlogn) 算法，请参阅 here它还提供了实现。