# Nicholas Rinard Keene's Little Bit

Download and view my resume (PDF)

## Thursday, June 27, 2013

### Longest Increasing Sequence (Small Solution)

This code finds the length of the Longest Increasing Sequence through adjacent numbers (including diagonals) in a rectangular grid of integers.
For example:
8 2 4
0 7 1
3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9), and cannot connect equal numbers (you could not connect 7 -> 7). The longest possible sequence for this example would be of length 5 by tracing the path 0->2->4->7->9 or 1->2->4->7->8.
```public class SmallCalcLIS {
public static void main(String[] args) {
int[][] values =   {{2, 4, 7, 7, 0, 0},
{3, 1, 4, 8, 0, 0},
{4, 0, 9, 0, 0, 0}};
System.out.println(longestIncreasingSequence(values));
}

static private int longestIncreasingSequence(int[][] values) {
int longestIncreasingSequence = 0;
for(int row = 0; row < values.length; row++) {
for(int col = 0; col < values[0].length; col++) {
if(lisFrom(values, row, col) > longestIncreasingSequence) longestIncreasingSequence = lisFrom(values, row, col);
}
}
return longestIncreasingSequence;
}

/**
* This recursive method calculates a 'longest increasing sequence' for a grid from a certain point.
* It does this by calling itself recursively for points neighboring the given point.
*
* This method is designed for minimum lines of code (for fun), not maximum efficiency. For instance,
* it makes up to twice as many recursive calls as it needs to.
*/
static private int lisFrom(int[][] values, int row, int col) {
int lis = 1;
if(row-1 >= 0 && row-1 < values.length && col   >= 0 && col   < values[0].length && values[row][col] < values[row-1][col])   if(lisFrom(values, row-1, col)   >= lis) lis = lisFrom(values, row-1, col)   + 1;
if(row-1 >= 0 && row-1 < values.length && col+1 >= 0 && col+1 < values[0].length && values[row][col] < values[row-1][col+1]) if(lisFrom(values, row-1, col+1) >= lis) lis = lisFrom(values, row-1, col+1) + 1;
if(row   >= 0 && row   < values.length && col+1 >= 0 && col+1 < values[0].length && values[row][col] < values[row][col+1])   if(lisFrom(values, row,   col+1) >= lis) lis = lisFrom(values, row,   col+1) + 1;
if(row+1 >= 0 && row+1 < values.length && col+1 >= 0 && col+1 < values[0].length && values[row][col] < values[row+1][col+1]) if(lisFrom(values, row+1, col+1) >= lis) lis = lisFrom(values, row+1, col+1) + 1;
if(row+1 >= 0 && row+1 < values.length && col   >= 0 && col   < values[0].length && values[row][col] < values[row+1][col])   if(lisFrom(values, row+1, col)   >= lis) lis = lisFrom(values, row+1, col)   + 1;
if(row+1 >= 0 && row+1 < values.length && col-1 >= 0 && col-1 < values[0].length && values[row][col] < values[row+1][col-1]) if(lisFrom(values, row+1, col-1) >= lis) lis = lisFrom(values, row+1, col-1) + 1;
if(row   >= 0 && row   < values.length && col-1 >= 0 && col-1 < values[0].length && values[row][col] < values[row][col-1])   if(lisFrom(values, row,   col-1) >= lis) lis = lisFrom(values, row,   col-1) + 1;
if(row-1 >= 0 && row-1 < values.length && col-1 >= 0 && col-1 < values[0].length && values[row][col] < values[row-1][col-1]) if(lisFrom(values, row-1, col-1) >= lis) lis = lisFrom(values, row-1, col-1) + 1;
return lis;
}
}```

#### 1 comment:

1. Can you post the better solution?