Fruits and Baskets
There are ‘N’ baskets, each containing some fruits. All baskets are placed in a single horizontal line. Kevin and Mark both are very hungry and so, they want to eat the fruits as much as possible. They have decided to select a basket from either end of the line only (formally, first or the last basket in that line only) and eat all the fruits in that basket. They will pick the baskets alternatively.
You have to tell how many maximum fruits Kevin can eat if both of them pick and eat the fruits optimally.
Kevin will pick the basket first.
The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain a single integer ‘N’ which represents the number of baskets. The second line of each test case will contain ‘N’ non-negative integers each separated by a single whitespace. These numbers will represent the number of fruits in each basket, respectively.
For each test case, return the maximum number of fruits Kevin can eat. Print the output of each test case in a separate line.
You don’t need to print anything, It has already been taken care of. Just implement the given function.
1 <= T <= 100 1 <= N <= 100 1 <= BASKET[i] <= 10^4 Where 'BASKET[i]' denotes the number of fruits in the ith basket. Time limit: 1 sec
The basic idea is to break the given problem into the smaller subproblems and then write the recursive code for them.
Let’s assume that baskets are in the range[ i, …, j ] where ‘i’ and ‘j’ represents the front and the rear of the line, respectively.
The flow of Recursion:
Let’s define the term “MFKE” which represents the maximum fruits that Kevin can eat in a particular range of baskets. Our problem is to find “MFKE” in the range [i, …, j].
If, ‘i’ = ‘j’ (means only a single basket is left unselected)
“MFKE” in the range [ i, …, i ] = 1
Else if, ‘i’ + 1 = ‘j’ (means there are two baskets left unselected)
“MFKE” in the range [ i, …, j ] = max( basket[ i ] , basket[ j ] ).
“MFKE” in the range [i, …, j] = max( basket[ i ] + min( “MFKE” in range [ (i+2), …, j ], “MFKE” in range [ (i+1), …, (j - 1) ] ), basket[ j ] + min( “MFKE” in range [ (i+1), …, (j-1) ], “MFKE” in range [ i, …, (j-2) ] ) )
We will here use a helper function that is recursive in nature. This function is used to compute the “MFKE” for all the subproblems.
int helper(vector<int> & baskets, int i, int j)
Where ‘BASKET’ represents the vector that contains baskets. And, ‘i’ and ‘j’ denotes the front and the rear baskets, respectively.
The steps are as follows:
- The given function Returns the helper function by passing parameters ‘BASKET’, 0, and ‘N’ - 1.
- In the helper function,
- If, ‘i’ = ‘j’ => return ‘BASKET[ i ]’.
- Else if, ( ‘i’ + 1 ) = ‘j’ => return max(‘BASKET[ i ]', ‘BASKET[ j ]')
- Else, return max(‘BASKET[ i ]' + min( helper(‘BASKET', ‘i’ + 2, ‘j’), helper(‘BASKET', ‘i’ + 1, ‘j’ - 1)), ‘BASKET[ j ]' + min( helper(‘BASKET', ‘i’ + 1, ‘j’ - 1), helper(‘BASKET', ‘i’ , ‘j’ - 2)) ).