CODEWITHSUNDEEP
javaarraysalgorithmmultidimensional-array
Anton Dozortsev
Anton Dozortsev

Reputation: 4902

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.

Upvotes: 1

Views: 569

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727047

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

Upvotes: 3

Related Questions