“This is my fourth day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

Given a matrix matrix, the values are positive, negative, and zero. The snake can drop to any position in the leftmost column with an initial increment of 0. The snake can move in any of three directions: up right, right or down right. The numbers along the way are added up as increases; But when the snake goes negative, it dies. Snakes have a power that they can use once: to turn a number in a cell into a negative number. Snakes can stop when they walk to any grid. Returns the maximum increase the snake can get.

A, analysis,

f(i,j)

Preliminary analysis: when the snake reaches a certain position from the optimal leftmost, the maximum growth value is obtained, and Max is obtained at each point

Further analysis: snakes have an ability, whether to use this ability.

F (I,j) : Returns two values

  1. The snake starts at some optimal left position and stops at (I,j) without using this ability once
  2. The snake starts at an optimal position on the left, stops at (I,j), and uses this ability once to get the maximum increase

Final answer: Max (2*M*N) M*N cells, each cell returns 2 answers, finally find Max

Try to model

Top left, left, and bottom left => current position. The snake can reach the current position in three cases

On the left is the best case of all possibilities where you don’t use your power once and you use your power once

If the snake descends from a leftmost column, and the optimal drop point, it can’t reach (I,j) without the ability, then no = -1

If the snake descends from one of the leftmost columns, and the optimal drop point, uses the power once, but can’t get to (I,j), then yes = -1

Current no: You were and you are not used once

Current yes: previously used or currently used, both cases

Second, the implementation

public static int walk(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) { Info cur = f(matrix, i, j); ans = Math.max(ans, Math.max(cur.no, cur.yes)); }}return ans;
}

public static class Info {
    public int no;
    public int yes;

    public Info(int n, int y) { no = n; yes = y; }}public static Info f(int[][] matrix, int i, int j) {
    if (j == 0) { / / the left column
        int no = Math.max(matrix[i][0] -1);
        int yes = Math.max(-matrix[i][0] -1);
        return new Info(no, yes);
    }
    // j > 0 is not in the left-most column
    int preNo = -1;
    int preYes = -1;
    Info pre = f(matrix, i, j - 1);
    preNo = Math.max(pre.no, preNo);
    preYes = Math.max(pre.yes, preYes);
    if (i > 0) {
        pre = f(matrix, i - 1, j - 1);
        preNo = Math.max(pre.no, preNo);
        preYes = Math.max(pre.yes, preYes);
    }
    if (i < matrix.length - 1) {
        pre = f(matrix, i + 1, j - 1);
        preNo = Math.max(pre.no, preNo);
        preYes = Math.max(pre.yes, preYes);
    }
    int no = preNo == -1 ? -1 : (Math.max(-1, preNo + matrix[i][j]));
    // The power is only used once.
    int p1 = preYes == -1 ? -1 : (Math.max(-1, preYes + matrix[i][j]));
    // The power is used only once.
    int p2 = preNo == -1 ? -1 : (Math.max(-1, preNo - matrix[i][j]));
    int yes = Math.max(Math.max(p1, p2), -1);
    return new Info(no, yes);
}
Copy the code

Third, summary

It feels like writing code in a literal way. Just write what you assume, and the code will be written!