300. Longest Increasing Subsequence

/**

 * 300. Longest Increasing Subsequence

 * Given an integer array nums, return the length of the longest strictly increasing subsequence.

 * A subsequence is a sequence that can be derived from an array by deleting some or no elements without

 * changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 * Example 1:

 * Input: nums = [10,9,2,5,3,7,101,18]

 * Output: 4

 * Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

 */

See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/dynamic/LongestIncreasingSubsequence.java

This is a very unique approach for the problem and can be repeated for other problems as well.

The approach is to iterate over the data and insert new number on its correct index in the array as found by Arrays.binarySearch routine. This will ensure that the new array has sorted data. The index where data is being inserted will determine the length of maximum sub sequence based on the current value being inserted. We can therefore record the max sub sequence length and increment it as the sequence length is increased.

Here is the code:

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    int len = 0;
    for (int num : nums) {
        //note you are searching the dp array on range 0 to len
        //where len signifies the max increasing sequence length
        int index = Arrays.binarySearch(dp, 0, len, num);
        if (index < 0) {
            //binary search returns (-index -1) if not found, so adjust to correct index
            index = -(index + 1);
        }
        dp[index] = num; //add the number to its correct index
        if (len == index) { //need to increment max length when index ==len, since index starts at 0
            len++;
        }
    }
    return len;
}