/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static int getMaxValue_solution1(int[][] values) {
int rows = values.length;
int cols = values[0].length;
int[][] maxValues = new int[rows][cols];
for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
int left = 0;
int up = 0;
if(i > 0) {
up = maxValues[i - 1][j];
}
if(j > 0) {
left = maxValues[i][j - 1];
}
maxValues
[i
][j
] = Math.
max(left, up
) + values
[i
][j
]; }
}
return maxValues[rows - 1][cols - 1];
}
public static int getMaxValue_solution2(int[][] values) {
int rows = values.length;
int cols = values[0].length;
int[] maxValues = new int[cols];
for(int i = 0; i < rows; ++i) {
for(int j = 0; j < cols; ++j) {
int left = 0;
int up = 0;
if(i > 0) {
up = maxValues[j];
}
if(j > 0) {
left = maxValues[j - 1];
}
maxValues
[j
] = Math.
max(left, up
) + values
[i
][j
]; }
}
return maxValues[cols - 1];
}
// ----------------------- TEST CODE -----------------------
private static void test
(String testName,
int[][] values,
int expected
) { if(getMaxValue_solution1(values) == expected) {
System.
out.
println(testName
+ ": solution1 passed."); }
else {
System.
out.
println(testName
+ ": solution1 FAILED."); }
if(getMaxValue_solution2(values) == expected) {
System.
out.
println(testName
+ ": solution2 passed."); }
else {
System.
out.
println(testName
+ ": solution2 FAILED."); }
}
private static void test1() {
int[][] values = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int expected = 29;
test("test1", values, expected);
}
private static void test2() {
int[][] values = {
{1, 10, 3, 8},
{12, 2, 9, 6},
{5, 7, 4, 11},
{3, 7, 16, 5}
};
int expected = 53;
test("test2", values, expected);
}
private static void test3() {
int[][] values = {
{1, 10, 3, 8}
};
int expected = 22;
test("test3", values, expected);
}
private static void test4() {
int[][] values = {
{1},
{12},
{5},
{3}
};
int expected = 21;
test("test4", values, expected);
}
private static void test5() {
int[][] values = {
{3}
};
int expected = 3;
test("test5", values, expected);
}
public static void main
(String [] args
) { test1();
test2();
test3();
test4();
test5();
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKICAgIHB1YmxpYyBzdGF0aWMgaW50IGdldE1heFZhbHVlX3NvbHV0aW9uMShpbnRbXVtdIHZhbHVlcykgewogICAgICAgIGludCByb3dzID0gdmFsdWVzLmxlbmd0aDsKICAgICAgICBpbnQgY29scyA9IHZhbHVlc1swXS5sZW5ndGg7CiAgICAgICAgCiAgICAgICAgaW50W11bXSBtYXhWYWx1ZXMgPSBuZXcgaW50W3Jvd3NdW2NvbHNdOwogICAgICAgIAogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCByb3dzOyArK2kpIHsKICAgICAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IGNvbHM7ICsraikgewogICAgICAgICAgICAgICAgaW50IGxlZnQgPSAwOwogICAgICAgICAgICAgICAgaW50IHVwID0gMDsKICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgaWYoaSA+IDApIHsKICAgICAgICAgICAgICAgICAgICB1cCA9IG1heFZhbHVlc1tpIC0gMV1bal07CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgICAgICAgICAgaWYoaiA+IDApIHsKICAgICAgICAgICAgICAgICAgICBsZWZ0ID0gbWF4VmFsdWVzW2ldW2ogLSAxXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgbWF4VmFsdWVzW2ldW2pdID0gTWF0aC5tYXgobGVmdCwgdXApICsgdmFsdWVzW2ldW2pdOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHJldHVybiBtYXhWYWx1ZXNbcm93cyAtIDFdW2NvbHMgLSAxXTsKICAgIH0KICAgIAogICAgcHVibGljIHN0YXRpYyBpbnQgZ2V0TWF4VmFsdWVfc29sdXRpb24yKGludFtdW10gdmFsdWVzKSB7CiAgICAgICAgaW50IHJvd3MgPSB2YWx1ZXMubGVuZ3RoOwogICAgICAgIGludCBjb2xzID0gdmFsdWVzWzBdLmxlbmd0aDsKICAgICAgICAKICAgICAgICBpbnRbXSBtYXhWYWx1ZXMgPSBuZXcgaW50W2NvbHNdOwogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCByb3dzOyArK2kpIHsKICAgICAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IGNvbHM7ICsraikgewogICAgICAgICAgICAgICAgaW50IGxlZnQgPSAwOwogICAgICAgICAgICAgICAgaW50IHVwID0gMDsKICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgaWYoaSA+IDApIHsKICAgICAgICAgICAgICAgICAgICB1cCA9IG1heFZhbHVlc1tqXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBpZihqID4gMCkgewogICAgICAgICAgICAgICAgICAgIGxlZnQgPSBtYXhWYWx1ZXNbaiAtIDFdOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBtYXhWYWx1ZXNbal0gPSBNYXRoLm1heChsZWZ0LCB1cCkgKyB2YWx1ZXNbaV1bal07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgcmV0dXJuIG1heFZhbHVlc1tjb2xzIC0gMV07CiAgICB9CiAgICAKICAgIC8vIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIFRFU1QgQ09ERSAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQogICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCB0ZXN0KFN0cmluZyB0ZXN0TmFtZSwgaW50W11bXSB2YWx1ZXMsIGludCBleHBlY3RlZCkgewogICAgICAgIGlmKGdldE1heFZhbHVlX3NvbHV0aW9uMSh2YWx1ZXMpID09IGV4cGVjdGVkKSB7CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbih0ZXN0TmFtZSArICI6IHNvbHV0aW9uMSBwYXNzZWQuIik7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4odGVzdE5hbWUgKyAiOiBzb2x1dGlvbjEgRkFJTEVELiIpOwogICAgICAgIH0KICAgICAgICAKICAgICAgICBpZihnZXRNYXhWYWx1ZV9zb2x1dGlvbjIodmFsdWVzKSA9PSBleHBlY3RlZCkgewogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4odGVzdE5hbWUgKyAiOiBzb2x1dGlvbjIgcGFzc2VkLiIpOwogICAgICAgIH0KICAgICAgICBlbHNlIHsKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHRlc3ROYW1lICsgIjogc29sdXRpb24yIEZBSUxFRC4iKTsKICAgICAgICB9CiAgICB9CiAgICAKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDEoKSB7CiAgICAgICAgaW50W11bXSB2YWx1ZXMgPSB7CiAgICAgICAgICAgIHsxLCAyLCAzfSwKICAgICAgICAgICAgezQsIDUsIDZ9LAogICAgICAgICAgICB7NywgOCwgOX0KICAgICAgICB9OwogICAgICAgIGludCBleHBlY3RlZCA9IDI5OwogICAgICAgIHRlc3QoInRlc3QxIiwgdmFsdWVzLCBleHBlY3RlZCk7CiAgICB9CiAgICAKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDIoKSB7CiAgICAgICAgaW50W11bXSB2YWx1ZXMgPSB7CiAgICAgICAgICAgIHsxLCAxMCwgMywgOH0sCiAgICAgICAgICAgIHsxMiwgMiwgOSwgNn0sCiAgICAgICAgICAgIHs1LCA3LCA0LCAxMX0sCiAgICAgICAgICAgIHszLCA3LCAxNiwgNX0KICAgICAgICB9OwogICAgICAgIGludCBleHBlY3RlZCA9IDUzOwogICAgICAgIHRlc3QoInRlc3QyIiwgdmFsdWVzLCBleHBlY3RlZCk7CiAgICB9CiAgICAKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDMoKSB7CiAgICAgICAgaW50W11bXSB2YWx1ZXMgPSB7CiAgICAgICAgICAgIHsxLCAxMCwgMywgOH0KICAgICAgICB9OwogICAgICAgIGludCBleHBlY3RlZCA9IDIyOwogICAgICAgIHRlc3QoInRlc3QzIiwgdmFsdWVzLCBleHBlY3RlZCk7CiAgICB9CiAgICAKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDQoKSB7CiAgICAgICAgaW50W11bXSB2YWx1ZXMgPSB7CiAgICAgICAgICAgIHsxfSwKICAgICAgICAgICAgezEyfSwKICAgICAgICAgICAgezV9LAogICAgICAgICAgICB7M30KICAgICAgICB9OwogICAgICAgIGludCBleHBlY3RlZCA9IDIxOwogICAgICAgIHRlc3QoInRlc3Q0IiwgdmFsdWVzLCBleHBlY3RlZCk7CiAgICB9CiAgICAKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgdGVzdDUoKSB7CiAgICAgICAgaW50W11bXSB2YWx1ZXMgPSB7CiAgICAgICAgICAgIHszfQogICAgICAgIH07CiAgICAgICAgaW50IGV4cGVjdGVkID0gMzsKICAgICAgICB0ZXN0KCJ0ZXN0NSIsIHZhbHVlcywgZXhwZWN0ZWQpOwogICAgfQogICAgCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgdGVzdDEoKTsKICAgICAgICB0ZXN0MigpOwogICAgICAgIHRlc3QzKCk7CiAgICAgICAgdGVzdDQoKTsKICAgICAgICB0ZXN0NSgpOwogICAgfQp9