Longest Increasing Subsequence

Problem Statement

In this problem, you are given an array of integers, nums. Your goal is to determine the length of the longest subsequence within this array that is strictly increasing. A subsequence is defined as a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Here, a strictly increasing subsequence means that each subsequent element in the subsequence is greater than the preceding one.

Examples

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.

Example 2

Input:

nums = [0,1,0,3,2,3]

Output:

4

Example 3

Input:

nums = [7,7,7,7,7,7,7]

Output:

1

Constraints

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Approach and Intuition

In order to tackle the problem of finding the longest strictly increasing subsequence, we can consider each element at a time and make use of the examples provided and the constraints:

1. From the examples provided:

   • For the array [10,9,2,5,3,7,101,18], the longest increasing subsequence is [2,3,7,101] which has a length of 4.
   • For the array [0,1,0,3,2,3], the subsequence [0,1,2,3] is strictly increasing and the length, similarly, is 4.
   • For [7,7,7,7,7,7,7], the elements are all the same, thus the only increasing subsequences possible are the elements themselves, leading to the longest length being 1.

   The solutions derived from these examples provide a practical understanding of what constitutes a strictly increasing subsequence.

2. Taking into account the constraints:

   • With nums.length being up to 2500, a naive approach that checks all possible subsequences would be computationally expensive. Therefore, efficiency is crucial.
   • Element values in the range from -10,000 to 10,000 imply that transformations based solely on the numerical values (like normalizing) aren’t as helpful since the range is broad, but all integer operations remain efficient.

Combining the insights from the examples and the constraints, a dynamic programming approach or a binary search based method (like the patience sorting algorithm) will be effective. The dynamic approach typically involves using an array to store the length of the longest subsequence ending at each element and computing it based on previously computed values, ensuring a polynomial time complexity compared to the exponential complexity of brute-force methods.

Solutions

class LongestIncreasingSubsequence {
    public int findLISLength(int[] elements) {
        ArrayList<Integer> lisSequence = new ArrayList<>();
        lisSequence.add(elements[0]);
    
        for (int idx = 1; idx < elements.length; idx++) {
            int currentElement = elements[idx];
            if (currentElement > lisSequence.get(lisSequence.size() - 1)) {
                lisSequence.add(currentElement);
            } else {
                int updateIndex = locatePosition(lisSequence, currentElement);
                lisSequence.set(updateIndex, currentElement);
            }
        }
            
        return lisSequence.size();
    }
        
    private int locatePosition(ArrayList<Integer> sequence, int value) {
        int low = 0;
        int high = sequence.size() - 1;
    
        while (low < high) {
            int mid = (low + high) / 2;
            if (sequence.get(mid) >= value) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
            
        return low;
    }
}