Show problems as
Classic problem #1043MediumArrayDynamic Programming

Partition Array for Maximum Sum

Real-world version: Grade the Orchard Rows
Tracked in this browser only
Read Partition Array for Maximum Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

An orchard is planted as one long line of rows. You are given yields, where yields[i] is the crop weight recorded for row i, and an integer span.

At grading time the manager cuts the line into consecutive blocks. Every row belongs to exactly one block, and a block holds at least one row and at most span rows. Each row is then written into the season report with the heaviest weight found anywhere in its own block, and the season figure is the sum of the written weights over all rows.

Return the largest season figure that some cut into blocks produces.

Examples

Example 1

Input
yields = [4, 1, 1, 12, 2, 6, 3], span = 3
Output
58

Cutting into the blocks [4], [1, 1, 12] and [2, 6, 3] writes 4, then 12 three times, then 6 three times, giving 4 + 36 + 18 = 58.

Example 2

Input
yields = [1, 1, 9], span = 2
Output
19

Cutting into the blocks [1] and [1, 9] writes 1, then 9 twice, giving 1 + 18 = 19.

Example 3

Input
yields = [6, 2, 5, 1, 8, 3, 4], span = 2
Output
42

Cutting into the blocks [6, 2], [5, 1], [8, 3] and [4] writes 12 + 10 + 16 + 4 = 42.

Constraints

  • 1 <= yields.length <= 500
  • 0 <= yields[i] <= 10^9
  • 1 <= span <= yields.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_graded_total(yields: list[int], span: int) -> int:
Java
public int maxGradedTotal(int[] yields, int span)

More on the same topics