Given an array of integers, the cost to change an element is the absolute difference between its initial value and its new value.
For example, if an element is initially 10, it can be changed to 7 or 13 for a cost of 3.
Task. Determine the minimum total cost to make the array sorted along its length — either non-decreasing (ascending) or non-increasing (descending).
Example
n = 6
arr = [0, 1, 2, 5, 6, 5, 7]
- Only
arr[5] = 5violates the ascending order. - If you increase that 5 to 6, the array becomes
arr' = [0, 1, 2, 5, 6, 6, 7] - Cost =
|5 - 6| = 1.
中文总结（含关键词）
目标是在 允许修改元素值并按改动绝对差计费 的前提下，使数组 整体非降或非升 ，并让 总代价最小 。可用 等序回归 (Isotonic Regression, PAV) 在线性时间求解非降情形；非升情形对数组反转再做一次，取两者更小。 时间 O(n)，空间 O(n)。
关键词：算法面试题、数组、贪心 / 动态规划、等序回归、面试辅助、面经。
VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Apple、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。
正文完
