Assignment #6: Maximum Increasing Subsequence

Covers

Sorting

Basic problem

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 24
the longest increasing sequence has length 10, consisting of entries (r,c) (row and column, starting at zero) as follows:
(5,0)	with value 12
(6,0)	with value 14
(6,1)	with value 15
(6,2)	with value 20
(7,2)	with value 44
(7,3)	with value 52
(7,4)	with value 54
(6,3)	with value 71
(5,3)	with value 74
(4,3)	with value 96
Note 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

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.

Strategy

Last summer, this was programming assignment #3 and was solved using recursion. This semester you MUST DO THIS WITHOUT RECURSION, using the following simple algorithm:
  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.

What To Submit

Submit complete source code and run your program on a small grid and a large grid. Your program must include code that prints the elapsed time required to solve each instance, and your output should display the elapsed time for each instance solved.