what's the problem about logic error in 2d Kadane algorithm?

44 Views Asked by At

I am implementing a program that calculates the maximum subtotal of a 2d array using the kadane algorithm. But, I got logic error. I think I made mistakes in for loop, but I can't find it.

This is the problematic part of my code.

void kadane2D(double array[][1000], int n)
{
    for (int i = 1; i < n; i++)
        for (int j = 0; j < n; j++)
            array[i][j] += array[i-1][j];

    double sums[n];
    double ans = sums[0];
    double a = sums[0];

    for(int top=1; top<n; top++){
        for(int bottom=top; bottom<n; bottom++)
        {
            for(int i=0; i<n; i++)
                sums[i] = array[bottom][i] - array[top-1][i];

            a = min(a, min_kadane1d(sums, n));
            ans = max(ans, kadane1d(sums, n));
        }
    }
    cout << a << endl;
    cout << ans << endl;
}
0

There are 0 best solutions below