Given an integer array, generate two adjacent subsequences, if possible, where one is strictly increasing and another is strictly decreasing.
Pair<List<Integer>, List<Integer>> getSubsequences(List<Integer> input) {
for (int I = 0; I < input.size(); I++) {
List<Integer> before = input.subList(0, i);
List<Integer> after = input.subList(i+1, input.size()-1);
if (isIncreasing(before) && isDecreasing(after)) {
return new Pair<List<Integer>, List<integer>(
input.subList(0, i),
input.subList(i+1, input.size()-1));
}
}
Return null;
}
boolean isIncreasing(List<Integer> input) {
List<integer> sorted = new ArrayList<Integer>(input);
sorted.sort();
Return sorted.equals(input);
}
Boolean isDecreasing(List<Integer> input) {
List<Integer> reversed = new ArrayList<>(Lists.reverse(input)); Return IsIncreasing(reversed); }
If the subsequences don’t have to be adjacent, we can a subsequence to be within the other. In such case, getSubsequences would expand to include the discovered subsequence and the remainder.
For (int i = 0; I < input.size(); I++)
{
For (int j = I+1; j < input.size(); j++)
{
List<Integer> section = input.subList(I,j);
If (isIncreasing(section) {
List<Integer> remainder = new ArrayList<>();
remainder.addAll(input.subList(0,I));
remainder.addAll(input.subList(j+1,input.size()-1));
if (isDecreasing(remainder)) {
return new Pair<List<Integer>, List<Integer>>(section, remainder);
}
}
}
}
