Anton Dozortsev - 1 year ago 49

Java Question

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

But now I need to implement opportunity

Example (in this matrix numbers with

`*`

3*,0,2

2*, 0, 0

0*, 3, 0

Result

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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];
}
```

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