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