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;
}
}
No comments:
Post a Comment