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

cangjie

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>

maxSumAfterPartitioning

Partition Array for Maximum Sum

Subsequence of Size K With the Largest Even Sum

subsequence-of-size-k-with-the-largest-even-sum

长度为 K 的最大偶数和子序列

Partition String Into Minimum Beautiful Substrings

partition-string-into-minimum-beautiful-substrings

将字符串分割为最少的美丽子字符串

Minimum Substring Partition of Equal Character Frequency

minimum-substring-partition-of-equal-character-frequency

分割字符频率相等的最少子字符串

Array

Dynamic Programming

给你一个整数数组 <code>arr</code>，请你将该数组分隔为长度 最多 为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。

&nbsp;

示例 1：

<pre>
输入：arr = [1,15,7,9,2,5,10], k = 3
输出：84
解释：数组变为 [15,15,15,9,10,10,10]</pre>

示例 2：

<pre>
输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
输出：83
</pre>

示例 3：

<pre>
输入：arr = [1], k = 1
输出：1
</pre>

&nbsp;

提示：

<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>