fork(8) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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.
https://ideone.com/2vLRMk
Max value of gift from a matrix
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!