Find the longest increasing sequence in a two-dimensional grid of numbers. A sequence is simply a series of adjacent squares. Squares may not be used twice. 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 msut 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 List of Strings; the size of the List is the number of rows. Then use a StringTokenizer.
initially, mark each square with a cost of 0. consider each square, going from largest value to smallest for each square change its cost to be 1 + max( cost of adjacent square)At the end of the algorithm, each square's cost represents the longest sequence of increasing numbers eminating from that square. The largest of those costs is the actual answer you need, and you can determine the paths by tracing through the costs.