FilesExpand file tree

 dev

/

LongestIncreasingSubsequence.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

59 lines (44 loc) · 1.43 KB

 dev

/

LongestIncreasingSubsequence.java

Top

File metadata and controls

• Code
• Blame

59 lines (44 loc) · 1.43 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

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;

}

}