Maximum Sum of Covered Array Elements Using Tiles - DP Array Interview

Question

## Problem You have an array `nums` of integers and an integer `tile_width`. You may place any number of tiles, each covering exactly `tile_width` consecutive indices. Tiles cannot overlap. The score of a placement is the sum of all `nums[i]` covered by at least one tile. Maximize the total score. ```python def max_tile_sum(nums: list[int], tile_width: int) -> int: ... ``` **Example:** ``` nums = [2, -1, 4, 3, -2, 5], tile_width = 2 Output: 14 Explanation: Place tile at [0,1] (sum=1), [2,3] (sum=7), [4,5] (sum=3) -> total=11. Better: place tile at [2,3] and [4,5] -> 7+3=10. Or [2,3] sum=7 and skip negatives. Optimal: tile [2,3]=7, tile[4,5]=3, tile[0,1]=1 -> 11. Or just tile [2,3]=7 if others hurt. Work through DP to find true maximum. ``` **Constraints:** `1 <= tile_width <= len(nums) <= 10^4`, values in [-10^4, 10^4]. ## Follow-ups - Define the DP recurrence clearly. What are the states? - How does the problem change if tiles can overlap? - Can you solve a variant where you must place exactly `m` tiles?

Maximum Sum of Covered Array Elements Using Tiles - DP Array Interview

Question Details

Full Details

Topics

More from Bloomberg