split-array-into-maximum-number-of-subarrays

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 an array <code>nums</code> consisting of non-negative integers.

We define the score of subarray <code>nums[l..r]</code> such that <code>l &lt;= r</code> as <code>nums[l] AND nums[l + 1] AND ... AND nums[r]</code> where AND is the bitwise <code>AND</code> operation.

Consider splitting the array into one or more subarrays such that the following conditions are satisfied:

<ul>
	<li>Each element of the array belongs to exactly one subarray.</li>
	<li>The sum of scores of the subarrays is the minimum possible.</li>
</ul>

Return the maximum number of subarrays in a split that satisfies the conditions above.

A subarray is a contiguous part of an array.

&nbsp;
Example 1:

<pre>
Input: nums = [1,0,2,0,1,2]
Output: 3
Explanation: We can split the array into the following subarrays:
- [1,0]. The score of this subarray is 1 AND 0 = 0.
- [2,0]. The score of this subarray is 2 AND 0 = 0.
- [1,2]. The score of this subarray is 1 AND 2 = 0.
The sum of scores is 0 + 0 + 0 = 0, which is the minimum possible score that we can obtain.
It can be shown that we cannot split the array into more than 3 subarrays with a total score of 0. So we return 3.
</pre>

Example 2:

<pre>
Input: nums = [5,7,1,3]
Output: 1
Explanation: We can split the array into one subarray: [5,7,1,3] with a score of 1, which is the minimum possible score that we can obtain.
It can be shown that we cannot split the array into more than 1 subarray with a total score of 1. So we return 1.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 106</code></li>
</ul>

maxSubarrays

Split Array Into Maximum Number of Subarrays

Greedy

Bit Manipulation

Array

给你一个只包含 非负&nbsp;整数的数组&nbsp;<code>nums</code>&nbsp;。

我们定义满足 <code>l &lt;= r</code>&nbsp;的子数组&nbsp;<code>nums[l..r]</code>&nbsp;的分数为&nbsp;<code>nums[l] AND nums[l + 1] AND ... AND nums[r]</code>&nbsp;，其中&nbsp;AND&nbsp;是按位与运算。

请你将数组分割成一个或者更多子数组，满足：

<ul>
	<li>每个 元素都&nbsp;只&nbsp;属于一个子数组。</li>
	<li>子数组分数之和尽可能&nbsp;小&nbsp;。</li>
</ul>

请你在满足以上要求的条件下，返回&nbsp;最多&nbsp;可以得到多少个子数组。

一个 子数组&nbsp;是一个数组中一段连续的元素。

&nbsp;

示例 1：

<pre>
输入：nums = [1,0,2,0,1,2]
输出：3
解释：我们可以将数组分割成以下子数组：
- [1,0] 。子数组分数为 1 AND 0 = 0 。
- [2,0] 。子数组分数为 2 AND 0 = 0 。
- [1,2] 。子数组分数为 1 AND 2 = 0 。
分数之和为 0 + 0 + 0 = 0 ，是我们可以得到的最小分数之和。
在分数之和为 0 的前提下，最多可以将数组分割成 3 个子数组。所以返回 3 。
</pre>

示例 2：

<pre>
输入：nums = [5,7,1,3]
输出：1
解释：我们可以将数组分割成一个子数组：[5,7,1,3] ，分数为 1 ，这是可以得到的最小总分数。
在总分数为 1 的前提下，最多可以将数组分割成 1 个子数组。所以返回 1 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 106</code></li>
</ul>