import java.util.HashMap;
import java.util.Map;
import java.util.NavigableSet;
import java.util.TreeSet;
class LIS
{
public static void printLIS (int [] input){
int size = input.length;
//create an empty ordered set s
NavigableSet<Integer> set = new TreeSet<>();
/*
parent [i] will store the predecessor of element with index i in the
LIS ending at element with index i
*/
Map
<Integer, Integer
> parent
= new HashMap
<>();
for (int i=0;i<size;i++){
set.add(input[i]);
/*
if element is not inserted at the end, then delete next greater element from set.
*/
if(input[i]!=set.last())
set.remove(set.ceiling(input[i]+1));
/*
if the element is the last, then it potentially can be part of the final answer, capture the
parent.
*/
if(set.last()==input[i])
parent.put(input[i], set.floor(input[i]-1));
}
print(parent, set.last());
}
private static void print
(Map
<Integer, Integer
> parent,
Integer lastElement
){ while (parent.get(lastElement)!=null){
System.
out.
println(lastElement
); lastElement=parent.get(lastElement);
}
System.
out.
println(lastElement
); }
public static void main
(String[] args
) { int[] arr = { 2, 6, 3, 4, 1, 2, 9, 5, 8 };
printLIS(arr);
}
}
aW1wb3J0IGphdmEudXRpbC5IYXNoTWFwOwppbXBvcnQgamF2YS51dGlsLk1hcDsKaW1wb3J0IGphdmEudXRpbC5OYXZpZ2FibGVTZXQ7CmltcG9ydCBqYXZhLnV0aWwuVHJlZVNldDsKCmNsYXNzIExJUwp7CglwdWJsaWMgc3RhdGljIHZvaWQgcHJpbnRMSVMgKGludCBbXSBpbnB1dCl7CgkJaW50IHNpemUgPSBpbnB1dC5sZW5ndGg7CgkJLy9jcmVhdGUgYW4gZW1wdHkgb3JkZXJlZCBzZXQgcwoJCU5hdmlnYWJsZVNldDxJbnRlZ2VyPiBzZXQgPSBuZXcgVHJlZVNldDw+KCk7CgogICAgICAgIC8qCiAgICAgICAgcGFyZW50IFtpXSB3aWxsIHN0b3JlIHRoZSBwcmVkZWNlc3NvciBvZiBlbGVtZW50IHdpdGggaW5kZXggaSBpbiB0aGUKICAgICAgICBMSVMgZW5kaW5nIGF0IGVsZW1lbnQgd2l0aCBpbmRleCBpCiAgICAgICAgICovCgkJTWFwPEludGVnZXIsIEludGVnZXI+IHBhcmVudCA9IG5ldyBIYXNoTWFwPD4oKTsKCgkJZm9yIChpbnQgaT0wO2k8c2l6ZTtpKyspewoJCQlzZXQuYWRkKGlucHV0W2ldKTsKCgogICAgICAgICAgICAvKgogICAgICAgICAgICBpZiBlbGVtZW50IGlzIG5vdCBpbnNlcnRlZCBhdCB0aGUgZW5kLCB0aGVuIGRlbGV0ZSBuZXh0IGdyZWF0ZXIgZWxlbWVudCBmcm9tIHNldC4KICAgICAgICAgICAgICovCgkJCWlmKGlucHV0W2ldIT1zZXQubGFzdCgpKQoJCQkJc2V0LnJlbW92ZShzZXQuY2VpbGluZyhpbnB1dFtpXSsxKSk7CgogICAgICAgICAgICAvKgogICAgICAgICAgICAgaWYgdGhlIGVsZW1lbnQgaXMgdGhlIGxhc3QsIHRoZW4gaXQgcG90ZW50aWFsbHkgY2FuIGJlIHBhcnQgb2YgdGhlIGZpbmFsIGFuc3dlciwgY2FwdHVyZSB0aGUKICAgICAgICAgICAgIHBhcmVudC4KICAgICAgICAgICAgICovCgkJCWlmKHNldC5sYXN0KCk9PWlucHV0W2ldKQoJCQkJcGFyZW50LnB1dChpbnB1dFtpXSwgc2V0LmZsb29yKGlucHV0W2ldLTEpKTsKCgoJCX0KCQlwcmludChwYXJlbnQsIHNldC5sYXN0KCkpOwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgcHJpbnQoTWFwPEludGVnZXIsIEludGVnZXI+IHBhcmVudCwgSW50ZWdlciBsYXN0RWxlbWVudCl7CgkJd2hpbGUgKHBhcmVudC5nZXQobGFzdEVsZW1lbnQpIT1udWxsKXsKCQkJU3lzdGVtLm91dC5wcmludGxuKGxhc3RFbGVtZW50KTsKCQkJbGFzdEVsZW1lbnQ9cGFyZW50LmdldChsYXN0RWxlbWVudCk7CgkJfQoJCVN5c3RlbS5vdXQucHJpbnRsbihsYXN0RWxlbWVudCk7Cgl9CgkKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB7CgkJaW50W10gYXJyICA9IHsgMiwgNiwgMywgNCwgMSwgMiwgOSwgNSwgOCB9OwoJCXByaW50TElTKGFycik7Cgl9Cn0=