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.
We first define an array suf of length n, where suf[i] represents the minimum value of the array nums from index i to index n - 1. We can traverse the array nums from back to front to compute the array suf.
Next, we define a variable pre to represent the prefix sum of the array nums. We traverse the first n - 1 elements of the array nums. For each index i, we add nums[i] to pre and calculate the split score score(i) = pre - suf[i + 1]. We use a variable ans to maintain the maximum value among all split scores.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| 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 |
Maximum Score of a Split 🔥 LeetCode 3788 | Prefix + Suffix Trick | Contest Problem • Study Placement • 141 views views
Watch 3 more video solutions →Practice Maximum Score of a Split with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor