How should I practice Maximum Sum with Tiles?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Maximum Sum with Tiles associated with Microsoft?

FastPrep tags this as a Microsoft coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Dynamic Programming

Maximum Sum with Tiles

Learn this problem

● MediumMicrosoftNEW GRADOA

See Microsoft hiring insights

Problem statement

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.

Function

microsoftSumWithTiles(A: int[]) → int

Examples

Example 1

A = [2, 3, 5, 2, 3, 4, 6, 4, 1]return = 25

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

Example 2

A = [1, 5, 3, 2, 6, 6, 10, 4, 7, 2, 1]return = 35

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

Example 3

A = [1, 2, 3, 3, 2]return = 10

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

A = [5, 10, 3]return = 15

Only one tile can be used.