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 can’t 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 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):
		if m > n:
			return sum(arr)
		max_f = sum(arr[:m])
		l = 0
		cur_sum = max_f
		while l < len(arr):
			cur_sum -= arr[l]
			if l + m < len(arr):
				cur_sum += arr[l + m]
				max_f = max(cur_sum, max_f)
			else:
				cur_sum += arr[int((l + m) % len(arr))]
				max_f = max(cur_sum, max_f)
			l += 1
		return max_f


class Solution:

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


class Solution:

	def maxFruits(self, arr, n, m):
		maxValue = 0
		sum = 0
		i = 0
		while i < n and i < m:
			sum += arr[i]
			i += 1
		maxValue = max(maxValue, sum)
		if i == n:
			return maxValue
		for j in range(n):
			sum -= arr[j]
			sum += arr[i]
			maxValue = max(maxValue, sum)
			i = (i + 1) % n
		return maxValue


class Solution:

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


class Solution:

	def maxFruits(self, arr, n, m):
		curr_sum = 0
		r = min(m, n)
		for i in range(r):
			curr_sum += arr[i]
		max_sum = curr_sum
		for i in range(r, n + r):
			if i < n:
				curr_sum = curr_sum + arr[i] - arr[i - r]
			else:
				curr_sum = curr_sum + arr[i % n] - arr[i - r]
			if curr_sum > max_sum:
				max_sum = curr_sum
		return max_sum


class Solution:

	def maxFruits(self, arr, n, m):
		arr = arr + arr[:m]
		pref_sum = [0] * len(arr)
		pref_sum[0] = arr[0]
		for i in range(1, len(arr)):
			pref_sum[i] = arr[i] + pref_sum[i - 1]
		max_sum = pref_sum[m - 1]
		for i in range(m, len(arr)):
			new_sum = pref_sum[i] - pref_sum[i - m]
			max_sum = max(max_sum, new_sum)
		return max_sum


class Solution:

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


class Solution:

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


class Solution:

	def maxFruits(self, arr, n, m):
		maxx = -float('inf')
		summ = 0
		i = 0
		while i < n and i < m:
			summ += arr[i]
			i += 1
		maxx = max(maxx, summ)
		if i == n:
			return maxx
		for j in range(n):
			summ -= arr[j]
			summ += arr[i]
			maxx = max(maxx, summ)
			i = (i + 1) % n
		return maxx


class Solution:

	def maxFruits_(self, arr, n, m):
		i = 0
		max_res = 0
		for i in range(n):
			sum_t = 0
			for j in range(m):
				if i + j >= n:
					l = i + j - n
				else:
					l = i + j
				sum_t = sum_t + arr[l]
			max_res = max(max_res, sum_t)
		return max_res

	def maxFruits__(self, arr, n, m):
		i = 0
		max_res = 0
		if m >= n:
			max_res = sum(arr)
			return max_res
		cir_arr = arr + arr[0:m]
		max_res = sum(arr[0:m])
		for i in range(1, n + m):
			max_res = max(max_res, sum(cir_arr[i:i + m]))
		return max_res

	def maxFruits(self, arr, n, m):
		i = 0
		max_res = 0
		if m >= n:
			max_res = sum(arr)
			return max_res
		sum_t = sum(arr[0:m])
		max_res = sum_t
		j = 0
		for i in range(m, n + m):
			sum_t = sum_t - arr[j] + arr[i % n]
			max_res = max(max_res, sum_t)
			j += 1
		return max_res


class Solution:

	def maxFruits(self, arr, n, m):
		max_ = 0
		(max_, curr_val) = (sum(arr[:m]), sum(arr[:m]))
		for i in range(1, len(arr)):
			if i + m - 1 < len(arr):
				curr_val = curr_val - arr[i - 1] + arr[i + m - 1]
			else:
				curr_val = curr_val - arr[i - 1] + arr[i + m - 1 - len(arr)]
			max_ = max(max_, curr_val)
		return max_


class Solution:

	def maxFruits(self, arr, n, m):
		left = 0
		right = m - 1
		total = sum(arr[:m])
		prev = total
		if m == n:
			return total
		while left != n:
			total -= arr[left]
			left += 1
			if right + 1 == n:
				right = -1
			right += 1
			total += arr[right]
			if total >= prev:
				prev = total
		return prev


class Solution:

	def maxFruits(self, arr, n, m):
		summ = 0
		for k in range(m):
			summ += arr[k]
		maxsum = max(0, summ)
		(i, j) = (0, m - 1)
		while i < n - 1:
			summ -= arr[i]
			i += 1
			j += 1
			summ += arr[j % n]
			maxsum = max(summ, maxsum)
		return maxsum


class Solution:

	def maxFruits(self, arr, n, m):
		Max = 0
		Sum = 0
		i = 0
		while i < n and i < m:
			Sum += arr[i]
			i += 1
		Max = max(Max, Sum)
		if i == n:
			return Max
		for j in range(n):
			Sum -= arr[j]
			Sum += arr[i]
			Max = max(Max, Sum)
			i = (i + 1) % n
		return Max


class Solution:

	def maxFruits(self, arr, n, m):
		if n <= m:
			return sum(arr)
		bag = sum(arr[0:m])
		max_bag = bag
		for i in range(m, n + m):
			bag += arr[i % n] - arr[(i - m) % n]
			if bag > max_bag:
				max_bag = bag
		return max_bag


class Solution:

	def maxFruits(self, arr, n, m):
		max_so_far = 0
		total_trees = n
		window_size = m
		if window_size >= total_trees:
			return sum(arr)
		for i in range(window_size):
			max_so_far += arr[i]
		maxSum = max_so_far
		start_idx = 0
		for i in range(window_size, total_trees + window_size):
			max_so_far = max_so_far - arr[start_idx] + arr[i % total_trees]
			maxSum = max(maxSum, max_so_far)
			start_idx += 1
		return maxSum


class Solution:

	def maxFruits(self, arr, n, m):
		beg = 0
		end = 0
		max_fruits = 0
		sum_fruits = 0
		time_spent = 0
		visited = []
		while beg < n:
			visited.append((beg, end))
			if time_spent < m:
				sum_fruits += arr[end]
				max_fruits = max(max_fruits, sum_fruits)
				time_spent += 1
				end += 1
			else:
				sum_fruits -= arr[beg]
				time_spent -= 1
				beg += 1
			end = end % n
		return max_fruits


class Solution:

	def maxFruits(self, arr, n, k):
		i = 0
		j = 0
		sm = 0
		mx = -1
		arr += arr[:k]
		while j < len(arr):
			sm += arr[j]
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				mx = max(mx, sm)
				sm -= arr[i]
				i += 1
				j += 1
		return mx


class Solution:

	def maxFruits(self, arr, n, m):
		if n < m and arr != []:
			return arr[0]
		(i, j) = (0, 0)
		curr_sum = 0
		maxi = 0
		arr = arr + arr
		while i < n:
			curr_sum += arr[j]
			if j - i + 1 == m:
				maxi = max(maxi, curr_sum)
				curr_sum = curr_sum - arr[i]
				i += 1
			j += 1
		return maxi


class Solution:

	def maxFruits(self, arr, n, m):
		s = 0
		for i in range(m):
			s = s + arr[i]
		a = s
		for i in range(m, m + n):
			s = s + arr[i % n] - arr[(i - m) % n]
			if s > a:
				a = s
		return a


class Solution:

	def maxFruits(self, arr, n, m):
		if m >= n:
			return sum(arr[0:n])
		start = 0
		sum_ = sum(arr[0:m])
		max_ = sum_
		for i in range(m, m + n):
			sum_ -= arr[start % n]
			sum_ += arr[i % n]
			max_ = max(max_, sum_)
			start += 1
		return max_


class Solution:

	def maxFruits(self, arr, n, m):
		if n <= m:
			return sum(arr)
		max_sum = 0
		for i in range(m):
			max_sum += arr[i]
		curr_max = max_sum
		i = m
		start = 0
		while start < n:
			curr_max = curr_max + arr[i] - arr[start]
			max_sum = max(max_sum, curr_max)
			i = (i + 1) % n
			start += 1
		return max_sum


class Solution:

	def maxFruits(self, arr, n, m):
		max_value = 0
		current_value = 0
		for j in range(m):
			current_value += arr[j]
		for i in range(0, n):
			if current_value > max_value:
				max_value = current_value
			start_value = arr[i]
			end_value = arr[m + i] if m + i < n else arr[m + i - n]
			current_value = current_value - start_value + end_value
		return max_value


class Solution:

	def maxFruits(self, arr, n, m):
		sumarray = [0] * n
		if n > m:
			for i in range(m):
				sumarray[0] += arr[i]
			max = sumarray[0]
			for i in range(1, n):
				sumarray[i] = sumarray[i - 1] + arr[(i + m - 1) % n] - arr[i - 1]
				if sumarray[i] > max:
					max = sumarray[i]
			return max
		else:
			max = 0
			for i in range(n):
				max += arr[i]
			return max


class Solution:

	def maxFruits(self, arr, n, m):
		if len(arr) <= m:
			return sum(arr)
		start = 0
		end = m - 1
		cursum = sum(arr[:m])
		maxsum = 0
		while start != len(arr):
			maxsum = max(maxsum, cursum)
			cursum -= arr[start]
			start += 1
			end += 1
			cursum += arr[end % len(arr)]
		return maxsum