Skip to content

fix: constant inputs in LongestIncreasingSubsequence::findLISLen #5160

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
vil02 merged 1 commit into from
May 17, 2024
Merged

fix: constant inputs in LongestIncreasingSubsequence::findLISLen #5160

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
fix: handle constant inputs in `LongestIncreasingSubsequence::findLIS… 
…Len`
  • Loading branch information
@vil02
vil02 committed May 16, 2024
commit ec10f949763dff4fce2376cca2f2ad9fe0a0d1bd
27 changes: 7 additions & 20 deletions src/main/java/com/thealgorithms/dynamicprogramming/LongestIncreasingSubsequence.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,28 +1,12 @@
package com.thealgorithms.dynamicprogramming;

import java.util.Scanner;

/**
* @author Afrizal Fikri (https://github.com/icalF)
*/
public final class LongestIncreasingSubsequence {
private LongestIncreasingSubsequence() {
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();

int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}

System.out.println(LIS(arr));
System.out.println(findLISLen(arr));
sc.close();
}

private static int upperBound(int[] ar, int l, int r, int key) {
while (l < r - 1) {
int m = (l + r) >>> 1;
Expand All @@ -36,7 +20,7 @@ private static int upperBound(int[] ar, int l, int r, int key) {
return r;
}

private static int LIS(int[] array) {
public static int LIS(int[] array) {
int N = array.length;
if (N == 0) {
return 0;
Expand Down Expand Up @@ -73,14 +57,17 @@ else if (array[i] > tail[length - 1]) {
*/
// A function for finding the length of the LIS algorithm in O(nlogn) complexity.
public static int findLISLen(int[] a) {
int size = a.length;
final int size = a.length;
if (size == 0) {
return 0;
}
int[] arr = new int[size];
arr[0] = a[0];
int lis = 1;
for (int i = 1; i < size; i++) {
int index = binarySearchBetween(arr, lis, a[i]);
int index = binarySearchBetween(arr, lis - 1, a[i]);
arr[index] = a[i];
if (index > lis) {
if (index == lis) {
lis++;
}
}
Expand Down
49 changes: 49 additions & 0 deletions src/test/java/com/thealgorithms/dynamicprogramming/LongestIncreasingSubsequenceTests.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,49 @@
package com.thealgorithms.dynamicprogramming;

import static org.junit.jupiter.api.Assertions.assertEquals;

import java.util.Arrays;
import java.util.List;
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 LongestIncreasingSubsequenceTests {
@FunctionalInterface
public interface IntArrayToInt {
int apply(int[] array);
}

@ParameterizedTest
@MethodSource("testCases")
public void testLongestIncreasingSubsequence(final int expected, final int[] input, final IntArrayToInt method) {
assertEquals(expected, method.apply(input));
}

private static Stream<Arguments> testCases() {
final Object[][] testData = {
{0, new int[] {}},
{1, new int[] {1}},
{1, new int[] {2, 2}},
{1, new int[] {3, 3, 3}},
{1, new int[] {4, 4, 4, 4}},
{1, new int[] {5, 5, 5, 5, 5}},
{2, new int[] {1, 2}},
{2, new int[] {1, 2, 2, 2, 2}},
{2, new int[] {1, 0, 2}},
{3, new int[] {1, 10, 2, 30}},
{3, new int[] {5, 8, 3, 7, 9, 1}},
{6, new int[] {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}},
{4, new int[] {10, 9, 2, 5, 3, 7, 101, 18}},
{4, new int[] {10, 10, 9, 9, 2, 2, 5, 5, 3, 3, 7, 7, 101, 101, 18, 18}},
{4, new int[] {0, 1, 0, 3, 2, 3}},
{2, new int[] {1, 1, 2, 2, 2}},
{3, new int[] {1, 1, 2, 2, 2, 3, 3, 3, 3}},
};

final List<IntArrayToInt> methods = Arrays.asList(LongestIncreasingSubsequence::LIS, LongestIncreasingSubsequence::findLISLen);

return Stream.of(testData).flatMap(input -> methods.stream().map(method -> Arguments.of(input[0], input[1], method)));
}
}