maximum-number-of-ways-to-partition-an-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed integer array <code>nums</code> of length <code>n</code>. The number of ways to partition <code>nums</code> is the number of <code>pivot</code> indices that satisfy both conditions:

<ul>
	<li><code>1 &lt;= pivot &lt; n</code></li>
	<li><code>nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]</code></li>
</ul>

You are also given an integer <code>k</code>. You can choose to change the value of one element of <code>nums</code> to <code>k</code>, or to leave the array unchanged.

Return the maximum possible number of ways to partition <code>nums</code> to satisfy both conditions after changing at most one element.

&nbsp;
Example 1:

<pre>
Input: nums = [2,-1,2], k = 3
Output: 1
Explanation: One optimal approach is to change nums[0] to k. The array becomes [3,-1,2].
There is one way to partition the array:
- For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.
</pre>

Example 2:

<pre>
Input: nums = [0,0,0], k = 1
Output: 2
Explanation: The optimal approach is to leave the array unchanged.
There are two ways to partition the array:
- For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0.
- For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.
</pre>

Example 3:

<pre>
Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
Output: 4
Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14].
There are four ways to partition the array.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>-105 &lt;= k, nums[i] &lt;= 105</code></li>
</ul>

waysToPartition

Maximum Number of Ways to Partition an Array

Partition Equal Subset Sum

partition-equal-subset-sum

分割等和子集

Partition to K Equal Sum Subsets

partition-to-k-equal-sum-subsets

划分为k个相等的子集

Array

Hash Table

Counting

Enumeration

Prefix Sum

给你一个下标从 0&nbsp;开始且长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;。分割&nbsp;数组 <code>nums</code>&nbsp;的方案数定义为符合以下两个条件的 <code>pivot</code>&nbsp;数目：

<ul>
	<li><code>1 &lt;= pivot &lt; n</code></li>
	<li><code>nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]</code></li>
</ul>

同时给你一个整数&nbsp;<code>k</code>&nbsp;。你可以将&nbsp;<code>nums</code>&nbsp;中&nbsp;一个&nbsp;元素变为&nbsp;<code>k</code>&nbsp;或&nbsp;不改变&nbsp;数组。

请你返回在 至多&nbsp;改变一个元素的前提下，最多&nbsp;有多少种方法 分割&nbsp;<code>nums</code>&nbsp;使得上述两个条件都满足。

&nbsp;

示例 1：

<pre>输入：nums = [2,-1,2], k = 3
输出：1
解释：一个最优的方案是将 nums[0] 改为 k&nbsp;。数组变为 [3,-1,2] 。
有一种方法分割数组：
- pivot = 2 ，我们有分割 [3,-1 | 2]：3 + -1 == 2 。
</pre>

示例 2：

<pre>输入：nums = [0,0,0], k = 1
输出：2
解释：一个最优的方案是不改动数组。
有两种方法分割数组：
- pivot = 1 ，我们有分割 [0 | 0,0]：0 == 0 + 0 。
- pivot = 2 ，我们有分割 [0,0 | 0]: 0 + 0 == 0 。
</pre>

示例 3：

<pre>输入：nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
输出：4
解释：一个最优的方案是将 nums[2] 改为 k 。数组变为 [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14] 。
有四种方法分割数组。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>-105 &lt;= k, nums[i] &lt;= 105</code></li>
</ul>