Different method but an error in runtime


#1

Hi, I now understand the approach used by others is DP which I should have done in the first place. I was fixated on adapting the 2D-Kadane here and was able to arrive at a solution. When submitted, my solution is fine for “Correctness” criterion but it is giving a “Runtime error” as “Segmentation Fault”. I am unable to generate that error
I included my solution below. Please help me out. Thanks in advance.

int Solution::solve(vector<vector > &A) {
int m=A.size();
int n=A[0].size();
if(m==0 or n==0) return 0;
if(A[m-1][n-1]<=0) return A[m-1][n-1];

//Approach is a modified Kadane O(n*(m+n)).
//If m<n, use rows instead of columns. It gets optimized to O(m*n).

int row_suffix_A[m][n];
int col_suffix_A[m][n];

//Suffix_Sum is calculated for each cell in its row and column.

for(int i=m-1;i>=0;i--)
{
    row_suffix_A[i][n-1]=A[i][n-1];
    if(i==m-1)  col_suffix_A[i][n-1]=A[i][n-1];
    else        col_suffix_A[i][n-1]=col_suffix_A[i+1][n-1]+A[i][n-1];
}

for(int j=n-1;j>=0;j--)
{
    col_suffix_A[m-1][j]=A[m-1][j];
    if(j==n-1)  row_suffix_A[m-1][j]=A[m-1][j];
    else        row_suffix_A[m-1][j]=row_suffix_A[m-1][j+1]+A[m-1][j];
}

for(int i=m-2;i>=0;i--)
{
    for(int j=n-2;j>=0;j--)
    {
        row_suffix_A[i][j]= row_suffix_A[i][j+1] + A[i][j];
        col_suffix_A[i][j]= col_suffix_A[i+1][j] + A[i][j];
    }
}

int max_subarray_sum=0;

//The maximum sum subarray with left and right columns fixed ranges from "pos" to "m-1".

for(int ileft=0;ileft<n;ileft++)
{
    int pos=m;

    int subarray_sum=0;
    
    for(int irigt=ileft;irigt<n;irigt++)
    {
        if(pos<m)   subarray_sum+=col_suffix_A[pos][irigt];
        
        if(pos==0)
        {
            if(max_subarray_sum<subarray_sum) {max_subarray_sum=subarray_sum;}
            continue;
        }
        
        while(row_suffix_A[pos-1][ileft]-row_suffix_A[pos-1][irigt]+A[pos-1][irigt]>0)
        {
            subarray_sum+=row_suffix_A[pos-1][ileft]-row_suffix_A[pos-1][irigt]+A[pos-1][irigt];
            pos--;
            if(pos==0)  break;
        }
        if(max_subarray_sum<subarray_sum) {max_subarray_sum=subarray_sum;}
    }
}
return max_subarray_sum;  

}


#2

SOLVED - Declaring row_suffix_A and col_suffix_A 2D-arrays as 2D-vectors worked.
Thanks to ShashankJoshi for pointing it out.


#3

Getting the same error, resolved by using vector of vector instead of 2d array.