Find the maximum contiguous subarray sum

Given an array arr[] of N integers arranged in a circular fashion. Your task is to find the maximum contiguous subarray sum.

Sample Input
3
7
8 -8 9 -9 10 -11 12
8
10 -3 -4 7 6 5 -4 -1
8
-1 40 -14 7 6 5 -4 -1
Sample Output
22
23
52
#include<stdio.h>
int main() {
  int t, n, arr[20], result[10], i, j, k, l, sum, maxSum=0;
  scanf("%d",&t);
  for(i=0;i<t;i++){
    scanf("%d",&n);
    for(j=0;j<n;j++){
      scanf("%d",&arr[j]);
    }
    for(j=0;j<n;j++){
      sum = 0;
      for(k=j,l=1;l<=n;l++,k++){
        sum += arr[k%n];
        if(maxSum<sum)
          maxSum = sum;
      }
    }
    result[i] = maxSum;
  }
  for(i=0;i<t;i++)
    printf("%d\n",result[i]);
  return 0;
}

No comments:

Post a Comment

Total Pageviews