Kadane's Algorithm (Finding The Maximum Contiguous Subsequence In A Two-Dimensional Sequence)

#include <iostream>

#include <cstring>

#include <climits>

#include <algorithm>

#include <cstdio>

using namespace std;

#define siz 100

int input[siz][siz];

int sum[siz];

int solve(int N){

    int max_ending_here,max_so_far,maximum=INT_MIN;

    for(int startx=0;startx<N;startx++){

        memset(sum, 0, N * sizeof(int));

        for(int x=startx;x<N;x++){

            max_ending_here=0;

            max_so_far=INT_MIN;

            for(int y=0;y<N;y++){

                sum[y]+=input[x][y];

                max_ending_here=max(0,max_ending_here+sum[y]);

                max_so_far=max(max_so_far,max_ending_here);

            }

            maximum=max(maximum,max_so_far);

        }

    }

    return maximum;

}

int main()

{

    int N,x;

    //cout<<INT_MIN<<endl;

    //freopen("input.txt","r",stdin);

    while(scanf("%d",&N)==1){

        for(int i=0;i<N;i++){

            for(int j=0;j<N;j++){

                scanf("%d",&x);

                input[i][j]=x;

            }

        }

        cout<<solve(N)<<endl;

    }

    return 0;

}