Watch 4 video solutions for Maximum Score of a Split, a medium level problem involving Array, Prefix Sum. This walkthrough by Study Placement has 141 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums of length n.
Choose an index i such that 0 <= i < n - 1.
For a chosen split index i:
prefixSum(i) be the sum of nums[0] + nums[1] + ... + nums[i].suffixMin(i) be the minimum value among nums[i + 1], nums[i + 2], ..., nums[n - 1].The score of a split at index i is defined as:
score(i) = prefixSum(i) - suffixMin(i)
Return an integer denoting the maximum score over all valid split indices.
Example 1:
Input: nums = [10,-1,3,-4,-5]
Output: 17
Explanation:
The optimal split is at i = 2, score(2) = prefixSum(2) - suffixMin(2) = (10 + (-1) + 3) - (-5) = 17.
Example 2:
Input: nums = [-7,-5,3]
Output: -2
Explanation:
The optimal split is at i = 0, score(0) = prefixSum(0) - suffixMin(0) = (-7) - (-5) = -2.
Example 3:
Input: nums = [1,1]
Output: 0
Explanation:
The only valid split is at i = 0, score(0) = prefixSum(0) - suffixMin(0) = 1 - 1 = 0.
Constraints:
2 <= nums.length <= 105-109āāāāāāā <= nums[i] <= 109Problem Overview: You are given a binary sequence and must choose a split position that divides it into a left and right part. The score is defined as the number of 0s in the left part plus the number of 1s in the right part. The task is to find the split that produces the maximum score.
Approach 1: Brute Force Enumeration (O(nĀ²) time, O(1) space)
The most direct approach is to try every possible split position. For each index i, treat it as the boundary between the left and right sections. Count the number of zeros from the start of the array to i, then count the number of ones from i+1 to the end. Add both counts to compute the score for that split. Track the maximum score across all splits. This approach is easy to reason about and demonstrates the problem definition clearly, but repeatedly scanning the array makes it inefficient. Each split requires two scans, leading to O(nĀ²) time complexity with constant extra space.
Approach 2: Prefix Sum + Enumeration (O(n) time, O(n) space)
The optimal solution avoids repeated counting by precomputing counts using prefix sums. First compute the total number of 1s in the entire array. Then iterate through the array once while maintaining the number of zeros seen so far on the left. At each split position, the right-side ones equal totalOnes - onesSeenSoFar. The score becomes zerosLeft + onesRight. Update the maximum score while iterating. This reduces the problem to a single pass with constant updates at each step.
This method works because the score at each split depends only on cumulative counts. Instead of recomputing values for every boundary, you reuse previously computed information. The technique is a common pattern when working with arrays where repeated range counts are needed. Prefix-style counting converts expensive repeated scans into constant-time lookups.
Recommended for interviews: Interviewers typically expect the Prefix Sum + Enumeration approach. Starting with the brute force solution shows you understand the scoring rule and the role of the split boundary. Optimizing it using cumulative counts demonstrates familiarity with prefix techniques and the ability to reduce O(nĀ²) scans to a single O(n) traversal. This pattern appears frequently in array problems that require evaluating every partition efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(nĀ²) | O(1) | Useful for understanding the scoring rule or when constraints are very small |
| Prefix Sum + Enumeration | O(n) | O(n) or O(1) with running counts | Preferred for interviews and large inputs where repeated counting must be avoided |