Skip to content

Instantly share code, notes, and snippets.

@yokolet
Last active March 29, 2017 04:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yokolet/b03affcb6dc7bc4d01f6d290c2e3296c to your computer and use it in GitHub Desktop.
Save yokolet/b03affcb6dc7bc4d01f6d290c2e3296c to your computer and use it in GitHub Desktop.
/*
Problem: Given an array of integers, find an increasing subsequence.
*/
public class LongestIncreasingSubsequence {
// complexity: time O(n^2), space: O(n)
static void findLIS(int[] ary) {
int[] lis = new int[ary.length];
int max = 0;
// initialize LIS for all indexes
for (int i=0; i<lis.length; i++) { lis[i] = 1; }
// compute optimized LIS values in bottom up manner
for (int i=1; i<lis.length; i++) {
for (int j=0; j<i; j++) {
if (ary[i] > ary[j] && lis[i] <lis[j] + 1) {
lis[i] = lis[j] + 1;
}
}
}
// find what index gave the maximum length
int index = 0;
for (int i=0; i<lis.length; i++) {
if (max < lis[i]) {
max = lis[i];
index = i;
}
}
System.out.println(max);
// print what are elements of the increasing subsequence
int cur = max - 1;
StringBuilder sb = new StringBuilder();
sb.append(ary[index]);
for (int i = index - 1; i >= 0; i--) {
if (lis[i] == cur) {
sb.insert(0, " ").insert(0, ary[i]);
cur--;
}
}
System.out.println(sb.toString());
}
public static void main(String[] args) {
findLIS(new int[]{5, 3, 4, 8, 6, 7});
findLIS(new int[]{ 10, 22, 9, 33, 21, 50, 41, 60 });
findLIS(new int[]{ 1, 12, 7, 0, 23, 11, 52, 31, 61, 69, 70, 2 });
}
}
/*
References:
http://algorithms.tutorialhorizon.com/dynamic-programming-longest-increasing-subsequence/
http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
http://www.programcreek.com/2014/04/leetcode-longest-increasing-subsequence-java/
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment