Alphabetic Exclusion:

Why not use a Hashmap???

Write a recursive function for f(n):

Computes the length of the longest sorted subsequence in the 0..n range of the array.


OH THAT CAT IS HIGH
0  1    2   3  4

f(0) = 1.  [From 0..0], we have one word in sorted order ("OH")

f(1) = 2.  [From 1..1], we have two words in sorted order ("OH" "THAT")

f(2) = 2.  "OH" "THAT"

f(3) = 2.

f(4) = 2.

So, how do you find f(n)?

Well, look at f(0), f(1), ..., f(n-1)?

Could you add the nth word to the list from [0..0]?  If so, f(n) MIGHT be the length of that list+1.  If not, f(n) could be the length of the list (without adding 1).

Could you add the nth word to the list from [0..1]?  If so, f(n) MIGHT be the length of that list +1.  If not, f(n) could be the length of the list (without adding 1).

And so forth and so on, f(n) will be the max of all the lengths we have computed.

DOG PLOW CHIMNEY DANCE ELEPHANT IDAHO JAGUAR


Ha ha ha.  Here's what we do for real.

f(n) is the length of the longest subsequence that ENDS with word n.

f(0)  longest subsequence that ends with DOG  is just DOG.  f(0) = 1.

f(1):  longest subsequnce that ends with PLOW.  PLOW comes after DOG so it could be DOG PLOW (length 2) or just PLOW (length 1).  f(1) = 2.

f(2):  longest subsequence that ends with CHIMNEY.  CHIMNEY does not come after DOG.  CHIMNEY does not come after PLOW.  So, it must just be CHIMNEY.  f(2) = 1.

f(3):  longest subsequence ending with DANCE.  DANCE does not come after DOG or PLOW.  It does come after CHIMNEY.  The best subsequence ending with CHIMNEY has length 1.  So, the best subsequence ending with DANCE has length 2.

f(4):  ELEPHANT.  ELEPHANT comes after DOG  f(0) is 1, so it could be 2.
          ELEPHANT does not come after PLOW.
          ELEPHANT comes after CHIMNEY.  f(2) is 1, so it could be 2.
          ELEPHANT does come after DANCE.  f(3) is 2, so it could be 3.
          The max of all these is 3.  So f(4) = 3.
f(5):  IDAHO.  Comes after DOG:  f(0) = 1, so possibly 2.
               Does not come after PLOW.
               Comes after CHIMNEY:  f(2)=1, so possibly 2.
               Comes after DANCE.  f(3) = 2, so possibly 3.
               Comes after ELEPHANT.  f(4) = 3, so possibly 4.
               Max is 4.  So f(5) = 4.
f(6):  JAGUAR.  Comes after DOG:  f(0) = 1, so possibly 2.
                Not PLOW.
                Comes after CHIMNEY:  f(2)=1 so possibly 2.
                Comes after DANCE.  f(3) = 2, so possibly 3.
                Comes after ELEPHANT.  f(4) = 3, so possibly 4.
                Comes after IDAHO.  f(5) =4 , so possibly 5.
                Max of these is 5.  f(6) = 5.

So once we find the longest path ending in each word.  The largest of these longest paths has to be the longest path total.

Largest of all these is 5.  So the length of the largest sorted subsequence is 5  (CHIMNEY DANCE ELEPHANT IDAHO JAGUAR).  With seven words total, we only have to eliminate two to make the list sorted.

Notice that f(n) is built from f(0), f(1), f(2)...f(n-1).  Perhaps you should recursion and a HashMap to store the results of the recursion.

Because there's no arithmetic involving large numbers, you shouldn't need to use BigInteger for this.