Uva 108 - Maximum Sum

Problem: 108 - Maximum Sum

Description:
We can solve this problem with O(N^3) order. Kadane's algorithm can be used to find the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number). The complexity of Kadane's algorithm for 1D array is O(N).

Read : Maximum subarray problem



Code:
-------

#include<stdio.h>

int main( void ){

    int N;
    int t = 0;
    int a[100][100];
    int pr[100];
    int S = 1<<31, s = 0, k, l,j;
    int i,x,z,f=0;
    /*freopen("108.in","r",stdin);*/

    while((scanf("%d",&N))==1){
   for(i=0;i<N;i++)
  for(j=0;j<N;j++)
   scanf("%d",&a[i][j]);
      S=1<<31;

      /*Kadan 2D algorithm- O(N^3)*/
      for( z = 0; z < N; z++){
        for(i = 0; i < N; i++) pr[i] = 0;
        for(x = z; x < N; x++){
            t = 0;
            s = 1<<31;
            j = 0;
            k = 0; l = 0;
            for(i = 0; i < N; i++){
                pr[i] = pr[i] + a[x][i];
                t = t + pr[i];
                if( t > s){
                    s = t;
                    k = i;
                    l = j;
                }
                if( t < 0 ){
                    t = 0;
                    j = i + 1;
                }
            }
            if( s > S)S = s;

        }
      }
      printf("%d\n",S);
    }

    return 0;
}