Last Updated: 16 Mar, 2021
Bird and maximum fruit-gathering
Easy
Asked in company
There are ‘N’ trees in a circle. Each tree has a fruit value associated with it. A ninja bird eyeing the fruits on the tree is blazingly fast. It can sit on a tree for 0.5 sec to gather all the fruits present on the tree no matter the number of fruits present in the tree and then the ninja bird can move to a neighboring tree. It takes the ninja 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.
You are given N and M (the total number of seconds the ninja bird has), and the fruit values of the trees. Your task is to maximize the total fruit value that the ninja bird can gather. The bird can start from any tree.
Note
All trees are in a circle.
For Example:
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 tree 2 and then to tree 3.
Hence, total number of gathered fruits = 1 + 3 + 5 = 9.
Input Format
The first line of input contains a single integer ‘T’ denoting the number of test cases for the problem.
The first line of each test case in the input contains two space-separated integers ‘N’ and ‘M’ denoting the number of trees and the seconds given to collect the fruits from the trees.
And the second line contains 'N' single space-separated integers, denoting the fruits on each tree.
Output Format:
For each test case, print a single line containing a single integer denoting the maximum number of fruits the ninja bird can gather in the given amount of time.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= M <= 5000
1 <= N <= 5000
1 <= ARR[i] <= 5000
Time Limit: 1 sec.
Approaches
We will iterate through the trees with the help of a nested loop. Where we will further loop for the given number of seconds ‘m’, checking for every sum that we obtain is the maximum sum or not and update the sum on each iteration if it is maximum.
The algorithm will be-
- We will run a loop from the starting tree of the given list.
- Now from every tree, we will run a loop and traverse the remaining trees and sum the fruits collected and now check if there exists a sum with a bigger value than our current sum.
- We will maintain a variable ‘max_so_far’ for finding the maximum sum that we have gotten initialised by 0.
- Now for each tree that we traverse, we will keep adding the fruits in the trees for the given number of seconds after which we will check if the ‘max_so_far’ is greater than the ‘max_sum’ that we want and update the ‘max_sum’ if ‘max_so_far’ is greater than ‘max_sum’.
- We finally return the ‘max_sum’.
The main observation here is that we now only need to find out the maximum sum of values of a window of size M (in a circular array of size N) as she has only M seconds of time with the ninja bird.
The algorithm will be -
- We first check whether given ‘M’ is greater than or equal to ‘N’ and return the sum of all elements if the condition is true.
- Else we calculate the sum of the first ‘M’ elements in ‘max_so_far’ and for maximizing the possible fruit collection sum and initialise it to the ‘max_sum’ variable. Now, we loop from the index ‘M’ in the array up to ‘N’+’M’ elements that we have. Now for each iteration:
- First, calculate the sum by leaving the first tree and including the tree at the ‘M’ index and store it in ‘max_so_far’.
- Now, we check whether the ‘max_so_far’ > ‘max_sum’ and update ‘max_sum’ with the value of ‘max_so_far’.
- Finally, we return the ‘max_sum’.