Java Reference
In-Depth Information
StringTokenizer st =
new
StringTokenizer(s) ;
int
length=0;
while
( st . hasMoreTokens () )
{
st . nextToken() ;
l e ng t h++;
}
Your next task is to find the longest increasing sequence, where a sequence starts at
an integer and moves right or down to the next integer (you are not allowed to go left or
up). The output of the program consists of a list of
(row, column)
items. For the numbers
in the example array, this is the output for the longest increasing sequence. Each cell is
represented as
(row, column)
, where counting starts at 0.
(5,0) (6,0) (6,1) (6,2) (7,2) (7,3) (7,4) (8,4)
{
}
.Notethattherecanbe
several longest sequences, where the program is required to print just one of them. A simple
way to solve the problem is to find the longest sequence starting from each number and
then return the longest of all the sequences. The longest sequence starting at an integer can
be defined recursively as a function of the longest sequences that starts from the integer to
the right and the longest sequence that starts from the integer below. For extra credit, try
to find a more ecient non-recursive solution. Think dynamic programming.
This sequence represents the numbers
12,14,15,20,44,52,54,76
