Easy Kadane's algorithm approach in C++


#1

int kadane(int aux[],int n)
{
int curr_sum=aux[0],max_so_far=aux[0],i;
for(i=1;i<n;i++)
{
curr_sum=max(curr_sum+aux[i],aux[i]);
max_so_far=max(max_so_far,curr_sum);
}
return max_so_far;
}
int Solution::solve(vector<vector>&matrix)
{
int i,j,m=matrix.size(),n=matrix[0].size();
for(i=1;i<m;i++)
{
for(j=0;j<n;j++)
{
matrix[i][j]+=matrix[i-1][j];
}
}
int r1,r2,res=INT_MIN;
int aux[1501];
for(r1=0;r1<m;r1++)
{
for(r2=r1;r2<m;r2++)
{
for(i=0;i<n;i++)
{
aux[i]=matrix[r2][i]-(r1>0?matrix[r1-1][i]:0);
}
res=max(res,kadane(aux,n));
}
}
return res;
}