fork(6) download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. public static int getMaxValue_solution1(int[][] values) {
  11. int rows = values.length;
  12. int cols = values[0].length;
  13.  
  14. int[][] maxValues = new int[rows][cols];
  15.  
  16. for(int i = 0; i < rows; ++i) {
  17. for(int j = 0; j < cols; ++j) {
  18. int left = 0;
  19. int up = 0;
  20.  
  21. if(i > 0) {
  22. up = maxValues[i - 1][j];
  23. }
  24.  
  25. if(j > 0) {
  26. left = maxValues[i][j - 1];
  27. }
  28.  
  29. maxValues[i][j] = Math.max(left, up) + values[i][j];
  30. }
  31. }
  32.  
  33. return maxValues[rows - 1][cols - 1];
  34. }
  35.  
  36. public static int getMaxValue_solution2(int[][] values) {
  37. int rows = values.length;
  38. int cols = values[0].length;
  39.  
  40. int[] maxValues = new int[cols];
  41. for(int i = 0; i < rows; ++i) {
  42. for(int j = 0; j < cols; ++j) {
  43. int left = 0;
  44. int up = 0;
  45.  
  46. if(i > 0) {
  47. up = maxValues[j];
  48. }
  49.  
  50. if(j > 0) {
  51. left = maxValues[j - 1];
  52. }
  53.  
  54. maxValues[j] = Math.max(left, up) + values[i][j];
  55. }
  56. }
  57.  
  58. return maxValues[cols - 1];
  59. }
  60.  
  61. // ----------------------- TEST CODE -----------------------
  62. private static void test(String testName, int[][] values, int expected) {
  63. if(getMaxValue_solution1(values) == expected) {
  64. System.out.println(testName + ": solution1 passed.");
  65. }
  66. else {
  67. System.out.println(testName + ": solution1 FAILED.");
  68. }
  69.  
  70. if(getMaxValue_solution2(values) == expected) {
  71. System.out.println(testName + ": solution2 passed.");
  72. }
  73. else {
  74. System.out.println(testName + ": solution2 FAILED.");
  75. }
  76. }
  77.  
  78. private static void test1() {
  79. int[][] values = {
  80. {1, 2, 3},
  81. {4, 5, 6},
  82. {7, 8, 9}
  83. };
  84. int expected = 29;
  85. test("test1", values, expected);
  86. }
  87.  
  88. private static void test2() {
  89. int[][] values = {
  90. {1, 10, 3, 8},
  91. {12, 2, 9, 6},
  92. {5, 7, 4, 11},
  93. {3, 7, 16, 5}
  94. };
  95. int expected = 53;
  96. test("test2", values, expected);
  97. }
  98.  
  99. private static void test3() {
  100. int[][] values = {
  101. {1, 10, 3, 8}
  102. };
  103. int expected = 22;
  104. test("test3", values, expected);
  105. }
  106.  
  107. private static void test4() {
  108. int[][] values = {
  109. {1},
  110. {12},
  111. {5},
  112. {3}
  113. };
  114. int expected = 21;
  115. test("test4", values, expected);
  116. }
  117.  
  118. private static void test5() {
  119. int[][] values = {
  120. {3}
  121. };
  122. int expected = 3;
  123. test("test5", values, expected);
  124. }
  125.  
  126. public static void main(String[] args) {
  127. test1();
  128. test2();
  129. test3();
  130. test4();
  131. test5();
  132. }
  133. }
Success #stdin #stdout 0.08s 380160KB
stdin
Standard input is empty
stdout
test1: solution1 passed.
test1: solution2 passed.
test2: solution1 passed.
test2: solution2 passed.
test3: solution1 passed.
test3: solution2 passed.
test4: solution1 passed.
test4: solution2 passed.
test5: solution1 passed.
test5: solution2 passed.