PracticeDynamic Programming

Peak Load Dispatch Plan

MediumDynamic Programmingtraversalstate trackingcomparison Time not estimated Not started

Context

A warehouse schedules shipments in a fixed dispatch order. Each shipment has a load rating, which may be positive, zero, or negative after adjustments. A valid dispatch plan selects shipments in order, with ratings strictly rising up to one peak and then strictly falling. Find the greatest possible total rating.

Problem

Given an integer array of shipment load ratings, choose a subsequence whose values strictly increase up to a peak and then strictly decrease after that peak. The increasing or decreasing side may be empty, so a single shipment and a monotonic subsequence are valid. Selected items must keep their original order, and skipped items are allowed. Return the largest possible sum of the selected ratings. Repeated values cannot be used for a strict increase or decrease.

Examples

Example 1

Input: loads = [2, 5, 9, 7, 3]

Output: 26

Explanation: For loads [2, 5, 9, 7, 3], the executed function returns 26.

Example 2

Input: loads = [1, 3, 5, 7]

Output: 16

Explanation: For loads [1, 3, 5, 7], the executed function returns 16.

Example 3

Input: loads = [-6, -2, -4, -8]

Output: -2

Explanation: For loads [-6, -2, -4, -8], the executed function returns -2.

Constraints

1 <= len(loads) <= 100
-10000 <= loads[i] <= 10000 for every i
Types: loads is int[]; result is int

Function signature

def maximum_peak_dispatch_sum(loads: list[int]) -> int

loads list[int]: Shipment load ratings in their fixed dispatch order.
returns int: The greatest sum among all valid strictly increasing-then-decreasing subsequences.

Adapted from MBPP problem task_245 (CC BY 4.0). Rewritten, extended and verified by Iksha.

Notes

A peak may be the first or last selected shipment.
The input is not required to be sorted, distinct, or positive.

Code

Saved

Checking environment…Python SandboxLn 1, Col 1

loads =