[Java] Find longest increasing or decreasing subsequence

 As second question from the last exercise, there was this. Given an input such as:

[
   [true, true, true, false],
   [true, false, false, false, false],
   [true, true, true, true, true, true, false, false]

]
 

Where each internal array ALWAYS has at least 2 elements and starts with a "true". Also, after the first "false" there can ONLY be "false" until the end of the array.

We calculate for each of these arrays the percentage of false elements over all elements, call it pct.

We then look for the longest strictly increasing pct sequence.

An empty input list or a list of only one element should return 0, in all other cases, the sequence starts counting AFTER the starting element.

This problem can be simplified by replacing each array with its calculated value, then it's just a linear walk on the input tracking and comparing at each step what is the longest sequence found so far.

There are however two things to note:

- do not forget to check at the end of the algorithm if the longest sequence was the whole array as in that case you wouldn't reach the break condition and therefore wouldn't update the result correctly

- the calculation for the percentage can be done in O(log(N)) time if we use binary search rather than scanning each array linearly since after the first occurrence of a "false" there can be only false

Using the code we wrote last time for a binary search for first occurrence we need to do a small adaptation in order to have our desired result. Boolean values are ordered naturally: false, true, while in our case we want the opposite. We can therefore tweak our method to accept a comparator in input so we now have a generic search that supports any ordering.

You can check my implementation of longestIncreasingFailedBuildSequence on my Gist along with some tests in LongestIncreasingFailedBuildSequence and you can find the inverted Boolean comparator in BooleanInvertedComparator