Kingdom War

• Time : $O(nm)$
• Space : $O(m)$

int Solution::solve(vector<vector<int>> &A) {
    int n = A.size(), m = A[0].size();
    int res = INT_MIN;
    vector<int> dp(m,0);
    for(int i = n - 1; i >= 0; i--) {
        int now = 0;
        for(int j = m - 1; j >= 0; j--) {
            dp[j] += A[i][j];
            now += dp[j];
            res = max(res, now);
        }
    }
    return res;
}