If you have no idea how to do it n^2


#1

Think about a question where there is a linear array and you have to find max sum of subarray with size B. Try it linearly. Apply the same thinking here. Also make sure to use union properties of sets (basic maths).


#2

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


#3

hi @Babuchak can you explain your approach a bit i am not able to comprehend the logic behind it.


#4

easier to see dp in this way: say B = 3. and you have dp[i - 1][j - 1], dp [i][j - 1] and dp[i - 1][j] where,
dp[i][j] stores sum of elements(not max sum, just sum):
[i, j], [i + 1, j], [i +2, j],
[i, j + 1], [i + 1, j + 1], [i + 2, j + 1],
[i, j + 2], [i + 1, j + 2], [i + 2, j + 2]
as 2 = B - 1.
Now say,
dp[i - 1][j - 1] :
x x x o
x x x o
x x x o
o o o

dp[i - 1][j] :
o x x x
o x x x
o x x x
o o o

dp[i][j - 1] :
o o o o
x x x o
x x x o
x x x

therefore, dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] :
n o o x
o x x x
o x x x
x x x

(‘n’ means its subtracted, ‘x’ means its added, ‘o’ means nothing)
now you just need to deal with four corners, to make it dp[i][j];

hence, dp[i][j] takes constant time for non - boundary i nd j.
for [0,0] it will take B^2.
for each j for i = 0 && for each i for j = 0, it can be calculate in B steps by sliding window.
while traversing keep max variable nd done.
so total steps = B^2 * (1) + B* (2 * (n - B)) + 1 * ((n- B)*(n- B)) = O(n^2).


#5
int Solution::solve(vector<vector<int>> &a, int b) {
    int n = a.size();
    vector<vector<int>> pre(n, vector<int>(n, 0));
    pre[0][0] = a[0][0];
    for(int i = 1;i < n; i++){
        pre[0][i] = pre[0][i-1] + a[0][i];
    }
    for(int j = 1; j < n; j++){
        pre[j][0] = pre[j-1][0] + a[j][0];
    }
    for(int i = 1; i < n; i++){
        for(int j = 1; j < n; j++){
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
        }
    }
    int ans = INT_MIN;
    for(int i = 0; i < n - b + 1; i++){
        for(int j = 0; j < n - b + 1; j++){
            int sum = 0;
            sum = pre[i + b-1][j + b-1];
            if(i >= 1)sum -= pre[i-1][j + b-1];
            if(j >= 1)sum -= pre[i + b-1][j-1];
            if(i >= 1 && j >= 1)sum += pre[i-1][j-1];
            ans = max(ans, sum);
        }
    }
    return ans;
}