This question was asked first in FACEBOOK On Campus for Internship.

#### Solution

#### Main Problem Statement : Hence Finally we need to get a Window of size X in Circular Array such that sum of the values of the Window is maximum.

#include<stdio.h> #include<math.h> int maxTreeSum(int a[], int size, int windowsize) { int max_so_far = 0, max_wind_start = -1; int i,j,sum=0; int w = windowsize; int n = size; for(i=0;i<n;i++){ for(j=0;j<w;j++){ sum=sum+a[(j+i)%n]; } if(max_so_far < sum){ max_wind_start=i ;max_so_far = sum; } sum=0; } printf("Max sum resulting window"); j=max_wind_start; while(w--){ printf(" %d",a[j%n]); j++; } printf("n"); return max_so_far; } int main() { int a[] = {2, 3, 4, 1, 2, 1, 5, 3}; //fruit values int n = sizeof(a)/sizeof(a[0]); // n int s = 3; //Bird has 3 seconds /* As Bird has 3 seconds it can stay at node for 0.5 sec + 0.5 sec to go to next node so bird can traverse 1 node in 1 sec hence in 3 seconds bird can traverse 3 node*/ int max_sum = maxTreeSum(a, n, s); printf("Maximum contiguous sum is %dn", max_sum); return 0; }

**Solution 2)**

**Optimized Solution with DP :**

First circular array is with fruit value.

Second circular array is with next all fruit values which a window of size S contains.

Instead storing smaller values as shown in diagram, we can store always maximum

eg 9,9,9..10,10

Idea here is to eliminate second loop of j to calculate sum of fruit values every time.

When we know that in next sum only last index value subtracted and next index value will be added

Solution from users awaited.

**Solution 3 : **

Instead using Another array in Solution 2) Keep only one variable max_so_far.

For i=0, calculate sum of fruits for next windows ( ie. if window is set 3 , then do)

for i=0,1,2 calculate max_so_far = a[0]+a[1]+a[2]; then for each i = 1 to n do following sum = max_so_far - a[i-1] + a[i+w-1]; if (sum < max_so_far ) { .... }

-> Basically instead searching every time in loop for sum or storing into auxiliary array. we fetched sum in one variable.

Complexity : O(N)

Space Complexity : O(1)