Problem Brief
Maximum Sum with Tiles
NEW GRADOA
See Microsoft online assessment and hiring insights
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.
1Example 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).
2Example 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).
3Example 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.
4Example 4
Input
A = [5, 10, 3]
Output
15
Explanation
Only one tile can be used.