# Split Array Into Maximum Number of Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/split-array-into-maximum-number-of-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/split-array-into-maximum-number-of-subarrays
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
You are given an array `nums` consisting of **non-negative** integers.

We define the score of subarray `nums[l..r]` such that `l <= r` as `nums[l] AND nums[l + 1] AND ... AND nums[r]` where **AND** is the bitwise `AND` operation.

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

* **E** **ach** element of the array belongs to **exactly** one subarray.
* The sum of scores of the subarrays is the **minimum** possible.

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

A **subarray** is a contiguous part of an array.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 106`

# Approaches
## Dynamic Programming
This approach solves the problem using dynamic programming. The core idea is to determine the maximum number of subarrays with a score of 0 for each prefix of the input array. We define `dp[i]` as the maximum number of valid subarrays for the prefix `nums[0...i-1]`. We build this `dp` table iteratively, considering all possible endpoints for the last subarray.
**Time:** O(N^2), where N is the length of the input array. There are two nested loops to populate the `dp` table. The outer loop runs N times, and the inner loop runs up to N times. · **Space:** O(N), for the `dp` array used to store the results of subproblems.
**Pros:** Provides a correct, structured way to solve the problem.; The logic is a direct translation of the subproblem definition, making it relatively easy to understand.
**Cons:** The O(N^2) time complexity is inefficient and will not pass the time limits for the given constraints (N up to 10^5).
### Explanation
First, we observe that the minimum possible sum of scores across all subarrays in any split is the bitwise AND of all elements in the entire array. Let this be `total_and`. If `total_and > 0`, the score of any subarray will be at least `total_and`. To minimize the sum, we must minimize the number of subarrays, which leads to a single subarray (the whole array). In this case, the answer is 1.

If `total_and == 0`, the minimum sum is 0. This can be achieved if we can partition the array into subarrays, each having a score of 0. Our goal is to maximize the number of such subarrays.

We can solve this using dynamic programming. Let `dp[i]` be the maximum number of subarrays `nums` can be split into using the prefix `nums[0...i-1]`, where each subarray has a score of 0.

- **State:** `dp[i]` = Maximum number of subarrays with score 0 for `nums[0...i-1]`.
- **Base Case:** `dp[0] = 0`.
- **Transition:** For each `i` from 1 to `n`, we compute `dp[i]` by trying all possible split points `j < i`. If the subarray `nums[j...i-1]` has a score of 0, we can potentially form a new subarray here. So, `dp[i]` will be the maximum of `dp[j] + 1` over all valid `j`.

`dp[i] = max({dp[j] + 1 | 0 <= j < i and AND(nums[j...i-1]) == 0})`

If after computing the table, `dp[n]` is 0 or less (our initial value), it means no such partition is possible, which implies `total_and > 0`. In that case, the answer is 1. Otherwise, the answer is `dp[n]`.

```java
import java.util.Arrays;

class Solution {
    public int maxSubarrays(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1); // Use -1 to indicate an unreachable state
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // Calculate AND of subarray nums[j...i-1]
                int currentAnd = -1; // Represents all bits set
                for (int k = j; k < i; k++) {
                    currentAnd &= nums[k];
                }

                if (currentAnd == 0) {
                    if (dp[j] != -1) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
        }

        // If dp[n] is -1, it means we couldn't split the array into
        // subarrays of score 0. This happens when the total AND > 0.
        // In that case, the answer is 1.
        return Math.max(1, dp[n]);
    }
}
```
An optimization to the inner loop can reduce the AND calculation from O(N) to O(1) by iterating `j` downwards, but the overall complexity remains O(N^2).
```java
// Optimized inner loop
for (int i = 1; i <= n; i++) {
    int currentAnd = -1;
    for (int j = i - 1; j >= 0; j--) {
        currentAnd &= nums[j];
        if (currentAnd == 0) {
            if (dp[j] != -1) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
}
```
### Algorithm
- First, handle the base case. The minimum possible sum of scores for any split is the bitwise AND of all elements in the array, let's call it `total_and`. If `total_and > 0`, the minimum sum is at least `total_and`. This minimum is achieved by taking the whole array as one subarray. Any other split would result in a sum greater than or equal to the number of subarrays times `total_and`. Thus, if `total_and > 0`, the answer is 1.
- If `total_and == 0`, the minimum possible sum is 0. This is achieved if we can split the array into subarrays that all have a score of 0.
- We use dynamic programming to find the maximum number of such subarrays. Let `dp[i]` be the maximum number of subarrays with a score of 0 that the prefix `nums[0...i-1]` can be partitioned into.
- The state transition is as follows: `dp[i] = max(dp[j] + 1)` for all `0 <= j < i` such that the subarray `nums[j...i-1]` has a bitwise AND score of 0.
- The base case is `dp[0] = 0`, representing an empty prefix having 0 subarrays.
- We compute `dp[i]` for `i` from 1 to `n`. The final answer for the `total_and == 0` case is `dp[n]`.
- Combining the cases, if `dp[n]` is positive, we return `dp[n]`. Otherwise (which corresponds to the `total_and > 0` case), we return 1.

## Greedy Approach with Bitwise AND Insight
This optimal approach uses a greedy strategy based on a key insight about the bitwise AND operation. The minimum possible sum of scores for any split is simply the bitwise AND of all elements in the array. If this total AND is positive, the answer must be 1. If it's zero, we can achieve a total score of zero by partitioning the array into subarrays that each have a score of zero. To maximize the number of such subarrays, we greedily find the shortest possible subarrays from left to right that satisfy this condition.
**Time:** O(N), where N is the length of the input array. We perform a single pass to calculate the total AND and another pass for the greedy splitting. · **Space:** O(1), as we only use a few variables to store the running AND value and the count.
**Pros:** Extremely efficient, with O(N) time complexity.; Requires only O(1) extra space.; The logic is simple to implement once the core idea is understood.
**Cons:** The proof of correctness for the greedy strategy relies on understanding the properties of the bitwise AND operation, which might not be immediately obvious.
### Explanation
The most efficient solution hinges on two key observations:

1.  **Minimum Sum of Scores:** The bitwise AND operation is monotonic non-increasing. That is, `a & b <= a` and `a & b <= b`. This means the score of any subarray `nums[l...r]` is greater than or equal to the score of any larger subarray that contains it. Consequently, the score of any subarray is greater than or equal to the bitwise AND of the entire array, `total_and = nums[0] & ... & nums[n-1]`. The sum of scores for any split is therefore at least `total_and`. This minimum sum is achievable by taking the whole array as one subarray. So, the minimum possible sum of scores is `total_and`.

2.  **Maximizing Subarrays:**
    -   If `total_and > 0`, the minimum sum is positive. To achieve this minimum sum, we must have only one subarray, so the answer is 1.
    -   If `total_and == 0`, the minimum sum is 0. We can achieve this by splitting the array into subarrays, each with a score of 0. To get the *maximum* number of subarrays, we should make each subarray as short as possible. This leads to a greedy strategy.

We iterate through the array, keeping track of the `current_and` of the subarray we are currently building. As soon as `current_and` becomes 0, we have found the shortest possible valid subarray starting from its beginning. We count this subarray and start a new one. Any elements left at the end of the array will be part of the last subarray. Since the `total_and` of the whole array is 0, this last segment, when combined with the preceding elements of its group, will also result in a score of 0.

This greedy approach correctly finds the maximum number of partitions because making each subarray as short as possible leaves the maximum number of elements for subsequent subarrays.

```java
class Solution {
    public int maxSubarrays(int[] nums) {
        // First, find the bitwise AND of the entire array.
        // This will be the minimum possible score for any split.
        int minPossibleScoreSum = -1; // Represents all bits set
        for (int num : nums) {
            minPossibleScoreSum &= num;
        }

        // If the minimum possible sum is greater than 0, we can't get any
        // subarray to have a score of 0. The best we can do is to take the
        // whole array as one subarray, with a score of minPossibleScoreSum.
        // So, the number of subarrays is 1.
        if (minPossibleScoreSum > 0) {
            return 1;
        }

        // If the minimum possible sum is 0, we need to find the maximum
        // number of subarrays we can split into, where each has a score of 0.
        // We use a greedy approach.
        int count = 0;
        int currentAnd = -1; // Represents all bits set

        for (int num : nums) {
            currentAnd &= num;
            if (currentAnd == 0) {
                // Found a subarray with score 0. Increment count and start a new one.
                count++;
                currentAnd = -1; // Reset for the next subarray
            }
        }

        // The count will be at least 1 if minPossibleScoreSum is 0.
        return count;
    }
}
```
### Algorithm
- First, calculate the bitwise AND of all elements in the array, let's call it `total_and`.
- The property of the bitwise AND operation implies that the score of any subarray is always greater than or equal to `total_and`. Therefore, the minimum possible sum of scores for any split is `total_and`.
- **Case 1: `total_and > 0`**. The minimum sum is `total_and`, which can only be achieved by having a single subarray (the entire array). Thus, the maximum number of subarrays is 1.
- **Case 2: `total_and == 0`**. The minimum sum is 0. This is achievable if we can split the array into subarrays that all have a score of 0. To maximize the number of subarrays, we should make each subarray as short as possible.
- We use a greedy strategy. Iterate through the array from left to right, maintaining the bitwise AND of the current subarray being formed.
- Initialize `count = 0` and `current_and = -1` (a number with all bits set).
- For each number in the input array, update `current_and` by ANDing it with the number.
- If `current_and` becomes 0, we have successfully formed a subarray with a score of 0. We increment our `count` and reset `current_and` to -1 to start forming a new subarray from the next element.
- The final `count` is the maximum number of subarrays. If `total_and` was 0, this count will be at least 1.

# Solutions
### Java

```java
class Solution {
public
  int maxSubarrays(int[] nums) {
    int score = -1;
    int ans = 1;
    for (int num : nums) {
      score &= num;
      if (score == 0) {
        ans++;
        score = -1;
      }
    }
    return ans == 1 ? 1 : ans - 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSubarrays(vector<int> &nums) {
    int score = -1, ans = 1;
    for (int num : nums) {
      score &= num;
      if (score == 0) {
        --score;
        ++ans;
      }
    }
    return ans == 1 ? 1 : ans - 1;
  }
};

```

### Python

```python
class Solution:
    def maxSubarrays(self, nums: List[int]) -> int: score, ans = - 1, 1 for num in nums: score &= num if score == 0: score = - 1 ans += 1 return 1 if ans == 1 else ans - 1

```