FastPrep

Description

Solutions

Maximum Sum with Tiles

👩‍🎓 NEW GRAD📚RELATED PROBLEMS

There is an array A of N integers and three tiles. Each tile can cover two neighbouring numbers from the array but cannot intersect with another tile. It also cannot be placed outside the array, even partially.

Write a function: def solution(A)

that, given an array A of N integers, returns the maximum sum of numbers that can be covered using at most three tiles.

Example 1:

Input:  A = [2, 3, 5, 2, 3, 4, 6, 4, 1]
Output: 25 
Explanation:

There is only one optimal placement of tiles: (3, 5), (3, 4), (6, 4).

Example 2:

Input:  A = [1, 5, 3, 2, 6, 6, 10, 4, 7, 2, 1]
Output: 35 
Explanation:

One of the three optimal placements of tiles is (5, 3), (6, 10), (4, 7).

Example 3:

Input:  A = [1, 2, 3, 3, 2]
Output: 10 
Explanation:
 
There is one optimal placement of tiles: (2, 3), (3, 2). Only two tiles can be used because A is too small to contain another one.

Example 4:

Input:  A = [5, 10, 3]
Output: 15 
Explanation:

Only one tile can be used.

Constraints:

:)