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:
-------
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; }
No comments:
Post a Comment