Overview of the problem of longest incremental subsequence

1. Overview of the longest incremental subsequence problem

1. Problem definition

Given a sequence of integers, e.g.nums = [10, 9, 2, 5, 3, 7, 101, 18], to find one of its longest subsequences so that the elements in this subsequence are strictly incremented.

In the above example, the longest incrementer sequence is[2, 3, 7, 101]or[2, 5, 7, 101]etc, length is 4.

2. Solutions and disadvantages of conventional dynamic programming

Ideas：

Usually one can be defineddparray, wheredp[i]Indicates thatnums[i]is the length of the longest incremental subsequence at the end.
The state transfer equation is generallydp[i] = max(dp[j]) + 1(in0 <= j < iandnums[j] < nums[i]), that is, iterate through all the previous ones less thannums[i]The corresponding elements ofdpValue, add 1 to updatedp[i]。
Finally, the longest incrementer sequence length of the entire sequence isdpThe maximum value in the array.

shortcoming：

The time complexity of this conventional solution is when the input sequence length is ,nWhen larger, the efficiency will be relatively low
Therefore, optimization is needed to reduce time complexity and improve solution efficiency

2. Optimization solution 1: Greedy + binary search (time complexity optimization to nlogn)

1. Greedy Thoughts

Maintain an arraytail, it is used to store the "tail" element of the longest incremental subsequence currently found. The length of this array actually represents the length of the longest incremental subsequence currently found (the initial length is 0).

For newly traversed elementsnums[i], We want to add it as reasonably as possible totailIn the array,tailThe array always maintains an ordered state (because the characteristics of the incremental sub-sequence determine that the "tail" element is incremented in an orderly manner), so that the longest incremental sub-sequence can be found efficiently through subsequent operations.

2. The use of binary search

Whenever a new element is traversednums[i]When we weretailFind the first one in the array by binary searchnums[i]Element positionpos(You can use the JavaThe binary search related method is implemented. If it is not found, the insertion point is returned, that is, the appropriate position).

ifposequaltailThe current length of the array, descriptionnums[i]It is larger than all the current "tail" elements, so it can be added to the new "tail" elementtailAt the end of the array, add 1 to the maximum incremental sub-sequence length, that istail = (tail, + 1); tail[ - 1] = nums[i];。
ifposLess thantailThe current length of the array, descriptionnums[i]Can be replacedtail[pos], because doing so will not destroy the properties of the amper sequence, and it is possible to find longer amper sequences later, i.e.tail[pos] = nums[i];。

3. Java code examples

import ;

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        int[] tail = new int[];
        int len = 0;
        for (int num : nums) {
            int pos = (tail, 0, len, num);
            if (pos &lt; 0) {
                pos = -(pos + 1);
            }
            tail[pos] = num;
            if (pos == len) {
                len++;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = lengthOfLIS(nums);
        ("The longest incremental sub-sequence length is: " + result);
    }
}

In the above code:

lengthOfLISThe method implements the optimized longest incremental subsequence solution logic. By constantly traversing the input arraynums, use binary search intailPosition the appropriate location in the array to updatetailArrays, while maintaining the length of the longest incremental subsequencelen。
mainThe method performs a simple test, passes in the example array and outputs the final calculated maximum incremental subsequence length.

3. Optimization solution 2: Dynamic programming + state compression (the time complexity is still O(n^2), but the space complexity is optimized)

1. Ideas

In the original dynamic programming solution, we used adpArray to record the longest incremental subsequence length ending with each element, but it is actually calculatingdp[i]When we only need to know that the previous element is smaller thannums[i]The corresponding elements ofdpThe value situation does not need to be used to correspond to all previous elements.dpAll values are saved intact.

Therefore, it can be compressed through state, using only one lengthn1D array to simulate dynamic programming process, each time the corresponding corresponding to the current element is updateddpWhen values are used, the values that were no longer needed are timely covered, thus saving space.

2. Java code examples

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        int n = ;
        int[] dp = new int[n];
        int maxLen = 1;
        for (int i = 0; i &lt; n; i++) {
            dp[i] = 1;
            for (int j = 0; j &lt; i; j++) {
                if (nums[j] &lt; nums[i]) {
                    dp[i] = (dp[i], dp[j] + 1);
                }
            }
            maxLen = (maxLen, dp[i]);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = lengthOfLIS(nums);
        ("The longest incremental sub-sequence length is: " + result);
    }
}

In this code example:

lengthOfLISIn the method, through a one-dimensionaldpArrays are used to dynamically plan and solve, and the inner loop is constantly updateddp[i]and maintain the maximum maximum incremental sub-sequence length in real timemaxLen, finally returnmaxLenAs a result.
mainThe method is also used in simple test scenarios, showing how to call itlengthOfLISMethod and output the result.

Through these optimization solutions, the longest incremental sub-sequence problem can be solved more efficiently, and the appropriate optimization method can be selected according to actual needs in different application scenarios and data scales to improve algorithm performance.

Summarize

The above is personal experience. I hope you can give you a reference and I hope you can support me more.