O(R*C) complexity using Kadane's Algorithm


#1

`int kadane(vector<vector> a,int n){

int curSum = a[0][0];
int maxSum = a[0][0];

for(int i=1;i<n;i++){
    curSum += a[i][0];
    curSum = max(curSum,a[i][0]);
    maxSum = max(curSum,maxSum);
}

return maxSum;

}

int Solution::solve(vector<vector > &mat)
{
int n= mat.size(),m = mat[0].size();
vector<vector> preSum(n,vector(1,0));
int res=INT_MIN;
for(int i=m-1;i>=0;i–){

   for(int j = 0;j<n;j++)
        preSum[j][0] += mat[j][i];
        
    int maxSoFar = kadane(preSum,n);
    res = max(res,maxSoFar);
}

return res;
}`

Total Computations : C * 2R