Using a grid of cells that holds values, try to find the maximum number of points that can be summed by using two traversals. The first traversal starts from the top left corner and ends in the bottom left corner. The second traversal starts from the top right corner and ends in the bottom right corner. You can move from one cell to the other in only three ways: down one cell, down one cell in a diagonal to the left, or down one cell in a diagonal to the right. If a cell is being visited by both traversals, then its value will be added to the sum only once.
​Input: int[][] startArray = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}, {17, 18, 19, 20} }; Output: 109 Explanation: The first traversal is: 1, 6, 11, 14, 17. The second one is: 4, 8, 12, 16, 20. |
Solution:
1. static final int ROW = 5; 2. static final int COLUMN = 4; 3. 4. static boolean isValidInput(int x, int y1, int y2) { 5. return ((x >= 0) && (x < ROW) && (y1 >= 0) && (y1 < COLUMN) && (y2 >= 0) && (y2 < COLUMN)); 6. } 7. 8. static int getMaxValue(int[][] startArray, int[][][] intermediaryValues, int x, int y1, int y2) { 9. if (!isValidInput(x, y1, y2)) { 10. return Integer.MIN_VALUE; 11. } 12. 13. if (x == ROW - 1 && y1 == 0 && y2 == COLUMN - 1) { 14. return startArray[x][y1] + startArray[x][y2]; 15. } 16. 17. if (x == ROW - 1) { 18. return Integer.MIN_VALUE; 19. } 20. 21. if (intermediaryValues[x][y1][y2] != -1) { 22. return intermediaryValues[x][y1][y2]; 23. } 24. 25. int answer = Integer.MIN_VALUE; 26. 27. int temporary = (y1 == y2) ? startArray[x][y1] : startArray[x][y1] + startArray[x][y2]; 28. 29. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1, y2 - 1)); 30. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1, y2 + 1)); 31. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1, y2)); 32. 33. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 - 1, y2)); 34. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 - 1, y2 - 1)); 35. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 - 1, y2 + 1)); 36. 37. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 + 1, y2)); 38. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 + 1, y2 - 1)); 39. answer = Math.max(answer, temporary + getMaxValue(startArray, intermediaryValues, x + 1, y1 + 1, y2 + 1)); 40. 41. return (intermediaryValues[x][y1][y2] = answer); 42. } 43. 44. static int geMaxCollectionValue(int[][] arr) { 45. int[][][] intermediaryValues = new int[ROW][COLUMN][COLUMN]; 46. for (int i = 0; i < ROW; i++) { 47. for (int j = 0; j < COLUMN; j++) { 48. for (int l = 0; l < COLUMN; l++) 49. intermediaryValues[i][j][l] = -1; 50. } 51. } 52. 53. return getMaxValue(arr, intermediaryValues, 0, 0, COLUMN - 1); 54. } 55.