Fruits and Baskets

Hard
0/120
Average time to solve is 50m
profile
Contributed by
16 upvotes
Asked in company
Adobe

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
6 4 5
4  
5 8 2 1
Sample Output 1:
10
9
Explanation of Sample Output 1:
In test case 1, Kevin will first select the front basket (containing 6 fruits) and then after Mark’s selection, he will pick fruits from the 2nd basket as Mark has already selected the 3rd basket.

In test case 2, The order of selection of baskets are as follows: -

Kevin - 4th (1), Mark - 1st (5), Kevin - 2nd (8), and Mark - 3rd (2).
Sample Input 2:
3
1
5
2
8 7
4
2 2 2 2
Sample Output 2:
5
8
4
Explanation for Sample Output 2:
In test case 1, there is only one basket and therefore, Kevin can only eat 5 fruits.

In test case 2, there are two baskets and Kevin wants to eat maximum fruits therefore, he will select 1st basket.

In test case 3, all baskets have the same number of fruits and so, Kevin can eat 2 + 2 = 4 fruits.
Hint

Try to break the problem into smaller subproblems.

Approaches (3)
Recursion

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

O(2 ^ N), Where ‘N’ is the total number of baskets.

 

Since we are calling two subproblems from the parent problem which follows recurrence relation: T(N) = 2 * T( N - 1) + C, so the overall time complexity will be O(2 ^ N).

Space Complexity

O(N), Where ‘N’ is the total number of baskets.

 

Since we are doing here recursive calls up to the single baskets remain so, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Fruits and Baskets
Full screen
Console