Skip to main content
Talentd

Maximum Score of a Split - Solution & Explanation

MediumArrayPrefix Sum8 min read
Practice this problem

Problem Statement

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:

  • Let prefixSum(i) be the sum of nums[0] + nums[1] + ... + nums[i].
  • Let 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] <= 109

Approach Overview

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

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(nĀ²)O(1)Useful for understanding the scoring rule or when constraints are very small
Prefix Sum + EnumerationO(n)O(n) or O(1) with running countsPreferred for interviews and large inputs where repeated counting must be avoided

Video Solution

Maximum Score of a Split šŸ”„ LeetCode 3788 | Prefix + Suffix Trick | Contest Problem ā€¢ Study Placement ā€¢ 148 views views

Watch 6 more video solutions ā†’

Frequently Asked Questions

Is Maximum Score of a Split easy or hard?
Maximum Score of a Split is generally classified as a Medium problem. The brute force idea is straightforward, but recognizing that prefix counting eliminates repeated scans is the key step that leads to the optimal O(n) solution.
Maximum Score of a Split Python/Java solution
In Python, Java, C++, Go, or TypeScript, the implementation iterates through the array once while maintaining counters for zeros and ones. At each split index, compute zerosLeft + onesRight and update the maximum value. The code typically fits in 10ā€“15 lines.
How to solve Maximum Score of a Split in O(n)?
First compute the total number of ones in the array. Then iterate through the array while tracking zeros on the left and ones seen so far. For each split position, calculate the score as zerosLeft plus (totalOnes minus onesSeenSoFar) and update the maximum score.
What is the best approach for Maximum Score of a Split?
The best approach is Prefix Sum with enumeration of split points. Maintain counts of zeros on the left and compute right-side ones using the total number of ones. This allows evaluating each split in constant time, producing an overall O(n) time complexity.
Is Maximum Score of a Split asked at Google/Amazon/Meta?
Problems using prefix sums and array partition scoring frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often involve maximizing metrics across a split or evaluating prefix and suffix contributions efficiently.
What data structure is used in Maximum Score of a Split?
The main technique uses prefix sums over an array or string. Instead of storing full prefix arrays, many implementations track running counts of zeros and ones during a single traversal to compute scores in constant time.
What is the time complexity of Maximum Score of a Split?
The optimal solution runs in O(n) time because the array is scanned once while maintaining running counts of zeros and ones. The brute force method requires O(nĀ²) time since each possible split recomputes counts across the array.

Ready to solve this problem?

Practice Maximum Score of a Split with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays