Find the longest increasing sequence in a two-dimensional grid of numbers. A sequence is simply a series of adjacent squares. Example: in the following grid:
97 47 56 36 60 31 57 54 12 55 35 57 41 13 82 80 71 93 31 62 89 36 98 75 91 46 95 53 37 99 25 45 26 17 15 82 80 73 96 17 75 22 63 96 96 36 64 31 99 86 12 80 42 74 54 14 93 17 14 55 14 15 20 71 34 50 22 60 32 41 90 69 44 52 54 73 20 12 55 52 39 33 25 31 76 45 44 84 90 52 94 35 55 24 41 63 87 93 79 24the longest increasing sequence has length 10, consisting of entries (r,c) (row and column, starting at zero) as follows:
(5,0) with cost 12 (6,0) with cost 14 (6,1) with cost 15 (6,2) with cost 20 (7,2) with cost 44 (7,3) with cost 52 (7,4) with cost 54 (6,3) with cost 71 (5,3) with cost 74 (4,3) with cost 96Note that the 96 adjacent to the 96 in the answer reported above could be substitued in the maximum increasing sequence, but both cannot be in the sequence, because the sequence must be strictly increasing.
The input file consists of the grid of numbers. You'll need to figure out the size of the grid. Read the file into an ArrayList of Strings; the size of the ArrayList is the number of rows. Then use a StringTokenizer.