Monday, August 13, 2012

Maximum contiguous sum in Circular Array


// find max contiguous sum in circular array
// INPUT : {8,-8,9,-9,10,-11,12} OUTPUT : 22
// INPUT : {1,-1,2,-1,1} OUTPUT : 3

#include<stdio.h>
#include<stdlib.h>

int findMaxContSum(int A[],int len){
int i,c,max;
for(i=0;i<len;i++){
//printf("%d\n",A[i]);
}
int *S = (int *)malloc(sizeof(int)*len);
int *start = (int *)malloc(sizeof(int)*len);
for(i=0;i<len;i++){
start[i] = -1;
}
S[0] = A[0];
start[0] = 0;
for(i=1;;i=(i+1)%len){
c = (i-1+len)%len;
if(start[i] == start[c]){
break;
}
if(S[c] + A[i] > A[i]){
S[i] = S[c] + A[i];
start[i] = start[c];
} else {
S[i] = A[i];
start[i] = i;
}
}
max = S[0];
for(i=1;i<len;i++){
if(S[i] > max){
max = S[i];
}
}
free(start);
free(S);
return max;
}

int main(){
//int A[] = {8,-8,9,-9,10,-11,12};
int A[] = {1,-1,2,-1,1};
int max = findMaxContSum(A,sizeof(A)/sizeof(int));
printf("%d",max);
return 0;
}

No comments:

Post a Comment