Repository: TheAlgorithms/Java
Pull request #6221 (2025-04-14 16:53:23)

Add LongestIncreasingSubsequenceNLogN class and corresponding test class
Hello, everyone! I added O(nlogn) solution of Longest Increasing Subsequence problem with simple and easy-to-follow explanations.

- [X] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [X] This pull request is all my own work -- I have not plagiarized it.
- [X] All filenames are in PascalCase.
- [X] All functions and variable names follow Java naming conventions.
- [X] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [X] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6221?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `89.47368%` with `2 lines` in your changes missing coverage. Please review.
> Project coverage is 73.80%. Comparing base [(`ce6e734`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/ce6e734ddee4fb9c4298cb59a0f97f11ddc41af2?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`cb7edc8`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/cb7edc8fd37011c0f132b18afa599dfc8908453b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6221?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...programming/LongestIncreasingSubsequenceNLogN.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6221?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdynamicprogramming%2FLongestIncreasingSubsequenceNLogN.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9keW5hbWljcHJvZ3JhbW1pbmcvTG9uZ2VzdEluY3JlYXNpbmdTdWJzZXF1ZW5jZU5Mb2dOLmphdmE=) | 89.47% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6221?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #6221      +/-   ##
============================================
+ Coverage     73.78%   73.80%   +0.01%     
- Complexity     5304     5311       +7     
============================================
  Files           672      673       +1     
  Lines         18357    18376      +19     
  Branches       3549     3553       +4     
============================================
+ Hits          13545    13562      +17     
- Misses         4265     4266       +1     
- Partials        547      548       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6221?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary> :rocket: New features to boost your workflow: </summary>

- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
</details>
DenizAltunkapan: LGM, but i think the actions will fail because there is no private constructor
huseynovvusal: > Looks good, thanks!

Glad to hear! 🎉

Patch:
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/LongestIncreasingSubsequenceNLogN.java b/src/main/java/com/thealgorithms/dynamicprogramming/LongestIncreasingSubsequenceNLogN.java
new file mode 100644
index 00000000..7bc0855e
--- /dev/null
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/LongestIncreasingSubsequenceNLogN.java
@@ -0,0 +1,75 @@
+package com.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)
+ */
+public final class LongestIncreasingSubsequenceNLogN {
+    private LongestIncreasingSubsequenceNLogN() {
+    }
+
+    /**
+     * 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.
+     */
+    private static int lowerBound(int[] arr, int target, int size) {
+        int l = 0;
+        int r = size;
+
+        while (l < r) {
+            int mid = 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
+        return l;
+    }
+
+    /**
+     * 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.
+     */
+    public static int lengthOfLIS(int[] arr) {
+        if (arr == null || arr.length == 0) {
+            return 0; // Return 0 for empty or null arrays
+        }
+
+        // tails[i] - the smallest end element of an increasing subsequence of length i+1
+        int[] tails = new int[arr.length];
+        // size - the length of the longest increasing subsequence found so far
+        int size = 0;
+
+        for (int x : arr) {
+            // Find the position to replace or extend the subsequence
+            int index = 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
+        return size;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/LongestIncreasingSubsequenceNLogNTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/LongestIncreasingSubsequenceNLogNTest.java
new file mode 100644
index 00000000..dc87d675
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/LongestIncreasingSubsequenceNLogNTest.java
@@ -0,0 +1,22 @@
+package com.thealgorithms.dynamicprogramming;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class LongestIncreasingSubsequenceNLogNTest {
+
+    private static Stream<Arguments> provideTestCases() {
+        return Stream.of(Arguments.of(new int[] {10, 9, 2, 5, 3, 7, 101, 18}, 4), Arguments.of(new int[] {0, 1, 0, 3, 2, 3}, 4), Arguments.of(new int[] {7, 7, 7, 7, 7}, 1), Arguments.of(new int[] {1, 3, 5, 4, 7}, 4), Arguments.of(new int[] {}, 0), Arguments.of(new int[] {10}, 1),
+            Arguments.of(new int[] {3, 10, 2, 1, 20}, 3), Arguments.of(new int[] {50, 3, 10, 7, 40, 80}, 4));
+    }
+
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    public void testLengthOfLIS(int[] input, int expected) {
+        assertEquals(expected, LongestIncreasingSubsequenceNLogN.lengthOfLIS(input));
+    }
+}