Anton Dozortsev - 1 year ago 53
Java Question

# Max sum path in 2D array + double two values to achieve better score

I have a 2d array and I need to find the max sum path that can be collected by left bottom and going only top and right until reach an end. I have done it on Java (task very similar to Project Euler: Problem 81):

``````static int maxSumPath(int[][] data) {
final int length = data.length;

final int[][] sumArr = new int[length][length];

for (int row = length - 1; row >= 0; row--) {
for (int col = 0; col < length; col++) {
if (row == length - 1 && col == 0) {
sumArr[row][col] = data[row][col];
} else if (row == length - 1) {
sumArr[row][col] = sumArr[row][col - 1] + data[row][col];
} else if (col == 0) {
sumArr[row][col] = sumArr[row + 1][col] + data[row][col];
} else {
sumArr[row][col] = Math.max(sumArr[row][col - 1], sumArr[row + 1][col]) + data[row][col];
}
}
}
return sumArr[0][length - 1];
}
``````

Example

3, 0, 2

2, 0, 0

0, 3, 0

Result 7.

But now I need to implement opportunity to double any value of that array to achieve better score and I can do it only twice and double certain value only once.

Example (in this matrix numbers with
`*`
must be doubled)

3*, 0, 2

2*, 0, 0

0*, 3, 0

Result 12.

You can solve this by adding a third dimension to your 2-D array, with exactly three layers:

``````final int[][][] sumArr = new int[3][length][length]
``````
• Layer zero represents the best sum you can get without doubling any elements
• Layer one represents the best sum you can get with doubling only one number
• Layer two represents the best sum you can get with doubling two numbers

The algorithm is a simple extension of what you already have, except now you need to set three partial sums in each branch of your `if` condition.

Here is your code modified according to the above:

``````static int maxSumPath(int[][] data) {
final int length = data.length;
final int[][][] sumArr = new int[3][length][length];
for (int row = length - 1; row >= 0; row--) {
for (int col = 0; col < length; col++) {
int val = data[row][col];
int val2 = data[row][col] * 2;
if (row == length - 1 && col == 0) {
sumArr[0][row][col] = val;
sumArr[1][row][col] = val2;
} else if (row == length - 1) {
sumArr[0][row][col] = sumArr[0][row][col - 1] + val;
sumArr[1][row][col] = Math.max(
sumArr[1][row][col - 1] + val
,   sumArr[0][row][col - 1] + val2
);
sumArr[2][row][col] = Math.max(
sumArr[1][row][col - 1] + val2
,   sumArr[2][row][col - 1] + val
);
} else if (col == 0) {
sumArr[0][row][col] = sumArr[0][row + 1][col] + val;
sumArr[1][row][col] = Math.max(
sumArr[0][row + 1][col] + val2
,   sumArr[1][row + 1][col] + val
);
sumArr[2][row][col] = Math.max(
sumArr[1][row + 1][col] + val2
,   sumArr[2][row + 1][col] + val
);
} else {
sumArr[0][row][col] = Math.max(
sumArr[0][row][col - 1], sumArr[0][row + 1][col]
) + data[row][col];
sumArr[1][row][col] = Math.max(
Math.max(sumArr[0][row][col - 1], sumArr[0][row + 1][col]) + val2
,   Math.max(sumArr[1][row][col - 1], sumArr[1][row + 1][col]) + val
);
sumArr[2][row][col] = Math.max(
Math.max(sumArr[1][row][col - 1], sumArr[1][row + 1][col])+val2
,   Math.max(sumArr[2][row][col - 1], sumArr[2][row + 1][col])+val
);
}
}
}
return sumArr[2][0][length - 1];
}
``````

Demo

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download