LongestIncreasingSubsequenceNLogN.java

packagecom.thealgorithms.dynamicprogramming;

/**
 * Implementation of the Longest Increasing Subsequence (LIS) problem using
 * an O(n log n) dynamic programming solution enhanced with binary search.
 *
 * @author Vusal Huseynov (https://github.com/huseynovvusal)
 */
publicfinalclassLongestIncreasingSubsequenceNLogN {
privateLongestIncreasingSubsequenceNLogN() {
 }

/**
 * Finds the index of the smallest element in the array that is greater than
 * or equal to the target using binary search. The search is restricted to
 * the first `size` elements of the array.
 *
 * @param arr The array to search in (assumed to be sorted up to `size`).
 * @param size The number of valid elements in the array.
 * @param target The target value to find the lower bound for.
 * @return The index of the lower bound.
 */
privatestaticintlowerBound(int[] arr, inttarget, intsize) {
intl = 0;
intr = size;

while (l < r) {
intmid = l + (r - l) / 2;

if (target > arr[mid]) {
// Move right if target is greater than mid element
l = mid + 1;
 } else {
// Move left if target is less than or equal to mid element
r = mid;
 }
 }

// Return the index where the target can be inserted
returnl;
 }

/**
 * Calculates the length of the Longest Increasing Subsequence (LIS) in the given array.
 *
 * @param arr The input array of integers.
 * @return The length of the LIS.
 */
publicstaticintlengthOfLIS(int[] arr) {
if (arr == null || arr.length == 0) {
return0; // Return 0 for empty or null arrays
 }

// tails[i] - the smallest end element of an increasing subsequence of length i+1
int[] tails = newint[arr.length];
// size - the length of the longest increasing subsequence found so far
intsize = 0;

for (intx : arr) {
// Find the position to replace or extend the subsequence
intindex = lowerBound(tails, x, size);

// Update the tails array with the current element
tails[index] = x;

// If the element extends the subsequence, increase the size
if (index == size) {
size++;
 }
 }

// Return the length of the LIS
returnsize;
 }
}