There are N trees in a circle. Each tree has a fruit value associated with it. A bird has to sit on a tree for 0.5 sec to gather all the fruits present on the tree and then the bird can move to a neighboring tree. It takes the bird 0.5 seconds to move from one tree to another. Once all the fruits are picked from a particular tree, she cant pick any more fruits from that tree. The maximum number of fruits she can gather is infinite.
Given N and M (the total number of seconds the bird has), and an array arr[] containing the fruit values of the trees. Maximize the total fruit value that the bird can gather. The bird can start from any tree.
 
Example 1:
Input:
N=7 M=3
arr[] = { 2 ,1 ,3 ,5 ,0 ,1 ,4 }
Output: 9
Explanation: 
She can start from tree 1 and move
to tree2 and then to tree 3.
Hence, total number of gathered fruits
= 1 + 3 + 5 = 9.
 
Example 2:
Input:
N=6 M=2
arr[] = { 1, 6, 2, 5, 3, 4 }
Output: 8
Explanation: 
She can start from tree 1 and move 
to tree 2. In this case she will gather
6 + 2 = 8 fruits. She can also start 
from tree 3 and move to tree 4. In this
case, too, she will gather 5 + 3 = 8 
fruits.
 
Your Task:
You don't need to read input, or print anything. You just need to complete the function maxFruits() that takes array arr, integer N and integer M as parameters and returns the maximum number of fruits she can gather.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
2 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def maxFruits(self,arr,n,m):



Solutions:
class Solution:

	def maxFruits(self, arr, n, m):
		sumo = sum(arr[:m])
		ans = sumo
		for i in range(1, n):
			sumo += arr[(i + m - 1) % n]
			sumo -= arr[i - 1]
			ans = max(ans, sumo)
		return ans


class Solution:

	def maxFruits(self, arr, n, m):
		if m >= n:
			return sum(arr)
		else:
			t = m
			amax = 0
			csum = 0
			for i in range(m):
				csum += arr[i]
			amax = csum
			while t < n + m:
				csum = csum - arr[(t - m) % n] + arr[t % n]
				amax = max(amax, csum)
				t += 1
		return amax


class Solution:

	def maxFruits(self, arr, n, m):
		i_left = 0
		i_right = m - 1
		if i_right >= n + 1:
			return sum(arr)
		m = sum(arr[i_left:i_right + 1])
		cur = m
		while i_left < n - 1:
			cur = cur + arr[(i_right + 1) % n] - arr[i_left % n]
			if cur > m:
				m = cur
			i_left += 1
			i_right += 1
		return m


class Solution:

	def maxFruits(self, arr, n, m):
		summa = sum(arr[:m])
		maxi = summa
		for i in range(n - m):
			summa += arr[i + m] - arr[i]
			maxi = max(maxi, summa)
		for i in range(m):
			summa += arr[i] - arr[i - m]
			maxi = max(maxi, summa)
		return maxi