Fruits and Baskets

PROBLEM STATEMENT

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.

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
1 <= BASKET[i] <= 10^4

Where 'BASKET[i]' denotes the number of fruits in the ith basket.

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:

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

Try Problem

Approach 2

The basic idea of this approach is to cut down the recursive calls for the overlapping subproblems using the top-down approach. All observations are the same as in approach 1.

Now, we have to also pass the ‘DP’ table in the helper function and so, the new definition of the helper function becomes:

int  helper(vector<int> & baskets, int i, int j, vector<vector<int>> & dp)

Where ‘BASKET’ and ‘DP’ represents the vector that contains baskets and the vector of vectors that is used as the 'DP' table. And, ‘i’ and ‘j’ denotes the front and the rear baskets, respectively.

The steps are as follows:

Create a two-dimensional ‘DP’ table of size ( ‘N’ * ‘N’ ), where ‘N’ is the number of baskets. Initially, fill the complete ‘DP’ table with the zeroes.
Return the helper function with parameters as ‘BASKET’, 0, ‘N’ - 1, and ‘DP’.
In the helper function,
- If, ‘i’ = ‘j’ => return ‘BASKET[ i ]'
- Else if, ( ‘i’ + 1 ) = ‘j’ => return max(‘BASKET[ i ]', ‘BASKET[ j ]')
- Else,
  - If, ‘DP[ ‘i’ ][ ‘j’ ]’ == 0 => Fill the ‘DP[ ‘i’ ][ ‘j’ ]’ with the max( ‘BASKET[ ‘i’ ]' + min( helper(‘BASKET', ‘i’ + 2, ‘j’, ‘DP’), helper(‘BASKET', ‘i’ + 1, ‘j’ - 1, ‘DP’)), ‘BASKET[ ‘j’ ]' + min( helper(‘BASKET', ‘i’ + 1, ‘j’ - 1, ‘DP’), helper(‘BASKET', ‘i’ ,'j' - 2, ‘DP’)) )
  - Else, return ‘DP[ i ][ j ]'.

Try Problem

Approach 3

The basic idea here is to use the bottom down approach of dynamic programming.

There is no helper function required in this approach. All observations are the same as in approach 1. We will fill the ‘DP’ table in the diagonal fashion so as to achieve the value at ‘DP[ 0 ][‘N’ - 1]’ at the end, after pre-calculating all the subproblems on which the value of dp[ 0 ][ ‘N’ - 1] is dependent.

The steps are as follows:

Create a ‘DP’ table of size ( ‘N’ * ‘N’ ).
Iterate through all the baskets i.e from 0 to ‘N’ (say, iterator = ‘k’).
- Iterate again from ‘k’ to ‘N’ (say, iterators = ‘j’ and ‘i’ where ‘i’ = 0 and ‘j’ = ‘k’)
  - Fill the ‘DP’ table at ‘DP[ i ][ j ]’ in the diagonal fashion.
Return the value of ‘DP[ 0 ][‘N’ - 1]’ as this is the required range for our problem.

Try Problem