Cheers

Mircea may be pretty right( links appreciated ), but I have a simple divide and conqueor approach. You can split the whole dna into 2 parts, the max sum will be the sum for left part, sum for right part and exactly one of the intervals overlapping with the mid point itself( this is very similar to the interval graph formulation from coloring problems ).

I am not sure of the complexity but it is definitely O(nmlogn). A more careful observation might make it much better.

I am trying to write a boggle solver right now.

What I have done so far is not to generate each possible path, but to move in each direction and see if that direction is a legal move. If it is, then I check whether the resulting “word” is (a) a prefix to a dictionary word, and (b) a dictionary word. The prefix is part is important because if it’s false, we don’t need to generate any more paths from that “word,” and that prunes some of the search space.

The adjacency list is not something I’d heard of (still new to this) so thank you for bringing it up. I have a feeling that it’s a very useful thing in general.

Using a real spell-checker… that is pretty clever
Here is a text-file Scrabble dictionary, if you want it, 6 months after posting, even: http://www.calvin.edu/~rpruim/scrabble/ospd3.txt