Split Array Into Maximum Number of Subarrays

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

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

1import java.util.Arrays;2 3class Solution {4    public int maxSubarrays(int[] nums) {5        int n = nums.length;6        int[] dp = new int[n + 1];7        Arrays.fill(dp, -1); // Use -1 to indicate an unreachable state8        dp[0] = 0;9 10        for (int i = 1; i <= n; i++) {11            for (int j = 0; j < i; j++) {12                // Calculate AND of subarray nums[j...i-1]13                int currentAnd = -1; // Represents all bits set14                for (int k = j; k < i; k++) {15                    currentAnd &= nums[k];16                }17 18                if (currentAnd == 0) {19                    if (dp[j] != -1) {20                        dp[i] = Math.max(dp[i], dp[j] + 1);21                    }22                }23            }24        }25 26        // If dp[n] is -1, it means we couldn't split the array into27        // subarrays of score 0. This happens when the total AND > 0.28        // In that case, the answer is 1.29        return Math.max(1, dp[n]);30    }31}

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

1// Optimized inner loop2for (int i = 1; i <= n; i++) {3    int currentAnd = -1;4    for (int j = i - 1; j >= 0; j--) {5        currentAnd &= nums[j];6        if (currentAnd == 0) {7            if (dp[j] != -1) {8                dp[i] = Math.max(dp[i], dp[j] + 1);9            }10        }11    }12}

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

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.

1class Solution {2    public int maxSubarrays(int[] nums) {3        // First, find the bitwise AND of the entire array.4        // This will be the minimum possible score for any split.5        int minPossibleScoreSum = -1; // Represents all bits set6        for (int num : nums) {7            minPossibleScoreSum &= num;8        }9 10        // If the minimum possible sum is greater than 0, we can't get any11        // subarray to have a score of 0. The best we can do is to take the12        // whole array as one subarray, with a score of minPossibleScoreSum.13        // So, the number of subarrays is 1.14        if (minPossibleScoreSum > 0) {15            return 1;16        }17 18        // If the minimum possible sum is 0, we need to find the maximum19        // number of subarrays we can split into, where each has a score of 0.20        // We use a greedy approach.21        int count = 0;22        int currentAnd = -1; // Represents all bits set23 24        for (int num : nums) {25            currentAnd &= num;26            if (currentAnd == 0) {27                // Found a subarray with score 0. Increment count and start a new one.28                count++;29                currentAnd = -1; // Reset for the next subarray30            }31        }32 33        // The count will be at least 1 if minPossibleScoreSum is 0.34        return count;35    }36}