Kingdom War

Two kingdoms are on a war right now, kingdom X and kingdom Y. As a war specialist of kingdom X, you scouted kingdom Y area.

A kingdom area is defined as a N x M grid with each cell denoting a village.
Each cell has a value which denotes the strength of each corresponding village.
The strength can also be negative, representing those warriors of your kingdom who were held hostages.

There’s also another thing to be noticed.

So your task is, find the largest sum of strength that you can erase by bombing one sub-matrix in the grid.

First line consists of 2 integers N and M denoting the number of rows and columns in the grid respectively.
The next N lines, consists of M integers each denoting the strength of each cell.

1 <= N <= 1500
1 <= M <= 1500
-200 <= Cell Strength <= 200

Output:

The largest sum of strength that you can get by choosing one sub-matrix.

Input:
3 3
-5 -4 -1
-3 2 4
2 5 8

Output:
19

Explanation:
Bomb the sub-matrix from (2,2) to (3,3): 2 + 4 + 5 + 8 = 19

Solution:

Time/Space: O(mn)

public class Solution {
    public int solve(int[][] A) {
        // dp[i][j] = max starting at i, j
        // dp[i][j] = dp[i + 1][j] + dp[i][j + 1] - dp[i + 1][j + 1] + A[i][j]
        // dp[m - 1][n - 1] = A[m - 1][n - 1]
        // max(dp[i][j])
        int m = A.length;
        int n = A[0].length;
        int[][] dp = new int[m][n];
        dp[m - 1][n - 1] = A[m - 1][n - 1];
        int max = A[m - 1][n - 1];
        for (int j = n - 2; j >= 0; j --) {
            dp[m - 1][j] = dp[m - 1][j + 1] + A[m - 1][j];
            max = Math.max(max, dp[m - 1][j]);
        }
        for (int i = m - 2; i >= 0; i --) {
            dp[i][n - 1] = dp[i + 1][n - 1] + A[i][n - 1];
            max = Math.max(max, dp[i][n - 1]);
        }
        for (int i = m - 2; i >= 0; i --) {
            for (int j = n - 2; j >= 0; j --) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1] - dp[i + 1][j + 1] + A[i][j];
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}

Space optimized:

public class Solution {
    public int solve(int[][] A) {
        // dp[i][j] = max starting at i, j
        // dp[i][j] = dp[i + 1][j] + dp[i][j + 1] - dp[i + 1][j + 1] + A[i][j]
        // dp[m - 1][n - 1] = A[m - 1][n - 1]
        // max(dp[i][j])
        int m = A.length;
        int n = A[0].length;
        int[] dp = new int[n];
        // dp[i + 1][j + 1]
        int pre = A[m - 1][n - 1];
        int max = A[m - 1][n - 1];
        dp[n - 1] = A[m - 1][n - 1];
        for (int j = n - 2; j >= 0; j --) {
            dp[j] = dp[j + 1] + A[m - 1][j];
            max = Math.max(max, dp[j]);
        }
        for (int i = m - 2; i >= 0; i --) {
            int temp = dp[n - 1];
            dp[n - 1] = dp[n - 1] + A[i][n - 1];
            max = Math.max(max, dp[n - 1]);
            pre = temp;
            for (int j = n - 2; j >= 0; j --) {
                temp = dp[j];
                // dp[i][j] = dp[i + 1][j] + dp[i][j + 1] - dp[i + 1][j + 1] + A[i][j];
                dp[j] = dp[j] + dp[j + 1] - pre + A[i][j];
                max = Math.max(max, dp[j]);
                pre = temp;
            }
        }
        return max;
    }
}