partition-array-for-maximum-sum

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

Given an integer array <code>arr</code>, partition the array into (contiguous) subarrays of length at most <code>k</code>. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.

&nbsp;
Example 1:

<pre>
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]
</pre>

Example 2:

<pre>
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
</pre>

Example 3:

<pre>
Input: arr = [1], k = 1
Output: 1
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr.length &lt;= 500</code></li>
	<li><code>0 &lt;= arr[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= arr.length</code></li>
</ul>