Java/DynamicProgramming/LongestIncreasingSubsequence.java at master · hankchen/Java · GitHub

History

59 lines (44 loc) · 1.43 KB

Raw

package DynamicProgramming;

import java.util.Scanner;

/** @author Afrizal Fikri (https://github.com/icalF) */

public class LongestIncreasingSubsequence {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int ar[] = new int[n];

for (int i = 0; i < n; i++) {

ar[i] = sc.nextInt();

}

System.out.println(LIS(ar));

sc.close();

}

private static int upperBound(int[] ar, int l, int r, int key) {

while (l < r - 1) {

int m = (l + r) >>> 1;

if (ar[m] >= key) r = m;

else l = m;

}

return r;

}

private static int LIS(int[] array) {

int N = array.length;

if (N == 0) return 0;

int[] tail = new int[N];

// always points empty slot in tail

int length = 1;

tail[0] = array[0];

for (int i = 1; i < N; i++) {

// new smallest value

if (array[i] < tail[0]) tail[0] = array[i];

// array[i] extends largest subsequence

else if (array[i] > tail[length - 1]) tail[length++] = array[i];

// array[i] will become end candidate of an existing subsequence or

// Throw away larger elements in all LIS, to make room for upcoming grater elements than

// array[i]

// (and also, array[i] would have already appeared in one of LIS, identify the location and

// replace it)

else tail[upperBound(tail, -1, length - 1, array[i])] = array[i];

}

return length;

}

Java/DynamicProgramming/LongestIncreasingSubsequence.java at master · hankchen/Java · GitHub

Expand file tree

Breadcrumbs

LongestIncreasingSubsequence.java

Latest commit

History

Breadcrumbs

LongestIncreasingSubsequence.java

File metadata and controls