Posted: 22 Feb, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### Note:

``````Kevin will pick the basket first.
``````
##### Input Format:
``````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.
``````
##### Output Format:
``````For each test case, return the maximum number of fruits Kevin can eat.

Print the output of each test case in a separate line.
``````
##### Note:
``````You don’t need to print anything, It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 100

Time limit: 1 sec
`````` Approach 1

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:

Observations:

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 ] ).

Else,

“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:

1. The given function Returns the helper function by passing parameters ‘BASKET’, 0, and ‘N’ - 1.
2. 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)) ).