uva 10827 - Maximum sum on a torusSolution

Algorithm : Kadane's Algorithm (calculate max sum for sub array)

Create 4 matrix for input matrix.
Suppose input is 4*4 then store it 8*8 matrix.

Suppose input 3*3 matrix

a1 a2 a3
b1 b2 b3
c1 c2 c3

store it 6*6 matrix like
a1 a2 a3 a1 a2 a3
b1 b2 b3 b1 b2 b3
c1 c2 c3 c1 c2 c3
a1 a2 a3 a1 a2 a3
b1 b2 b3 b1 b2 b3
c1 c2 c3 c1 c2 c3

calculate max sum for all 3*3 size matrix.

Code:

#include<iostream>
#include<algorithm>

using namespace std;

int max_sum_sub_array(int *arr,int n){
int max,i,cur_sum;
max=cur_sum=arr[0];
for(i=1;i<n;i++){
if(cur_sum<0)
cur_sum=0;
if(max<0 && arr[i]<0){
if(max<arr[i])
max=arr[i];
}else{
cur_sum=cur_sum+arr[i];
if(max<cur_sum)
max=cur_sum;
}
}
return max;
}

int main(){
int arr[160][160],i,j,k,n,kase,temp[160],max,ans,x,y;
cin>>kase;
while(kase--){
cin>>n;
max=0x80000000;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cin>>arr[i][j];
arr[i+n][j]=arr[i][j+n]=arr[i+n][j+n]=arr[i][j];
}
}

for(x=1;x<=n;x++){
for(y=1;y<=n;y++){
fill(temp,temp+n,0);
for(i=x;i<x+n;i++){
for(j=y,k=0;j<y+n;j++,k++){
temp[k]=temp[k] + arr[i][j];
}
ans=max_sum_sub_array(temp,n);
if(ans>max)
max=ans;
}
}
}
cout<<max<<endl;
}
return 0;
}