Best Total After Bounded Block Replacement

### Problem Split `arr` into nonempty contiguous blocks, each containing at most k elements. Replace every element in a block by that block's largest original value. Return the greatest possible total after all replacements. The source guarantees the optimum fits a signed 32-bit integer. ```cpp class Solution { public: int maxSumAfterPartitioning(vector<int>& arr, int k); }; ``` ### Examples **Example 1:** ```text Input: arr = [2,6,1,4], k = 2 Output: 20 Explanation: Blocks[2,6] and[1,4] contribute12 and8. The other possible boundaries give totals no larger than20. ``` **Example 2:** ```text Input: arr = [3,0,5], k = 3 Output: 15 Explanation: One block replaces all three values by5, reaching the upper bound3*5. ``` ### Constraints - The array contains 1 to 500 integers. - Every element is in `[0,1000000000]`. - `1 <= k <= arr.length`. - The optimal total fits a signed 32-bit integer. ### Contract considerations Blocks preserve the input order and cover every element exactly once. The return value is a total, not a proposed partition. ```hint Read the boundary condition How should a block shorter than k and an original zero value be treated under the same partition rules? ``` ### Boundary reminders Blocks preserve the input order and cover every element exactly once. The return value is a total, not a proposed partition.