3788. Maximum Score of a Split

MediumArrayPrefix Sum

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n.

Your task is to choose a split index i such that 0 <= i < n - 1. This split divides the array into two parts: a prefix (from index 0 to i) and a suffix (from index i + 1 to n - 1).

For a chosen split index i, two values are defined:

prefixSum(i): the sum of all elements in the prefix, i.e., nums[0] + nums[1] + ... + nums[i].
suffixMin(i): the minimum value among all elements in the suffix, i.e., the smallest of nums[i + 1], nums[i + 2], ..., nums[n - 1].

The score of a split at index i is then defined as:

score(i) = prefixSum(i) - suffixMin(i)

You need to return an integer representing the maximum score that can be obtained over all valid split indices i.

In other words, for every possible position where you can cut the array into a non-empty prefix and a non-empty suffix, compute the difference between the prefix sum and the suffix minimum, and return the largest such difference.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sums?

This problem maps to Prefix Sums through a short path in the full flowchart.

Computing prefix sums incrementally while precomputing suffix minimums lets us evaluate every possible split index in O(n).

Open in Flowchart

Intuition

To find the maximum score, we need to evaluate score(i) = prefixSum(i) - suffixMin(i) for every valid split index i. A direct approach would be to recompute the prefix sum and suffix minimum from scratch for each i, but that would be wasteful and slow.

The key observation is that both prefixSum(i) and suffixMin(i) can be computed incrementally rather than recalculated every time.

For the prefix sum, notice that as we move the split index i from left to right, the prefix sum only grows by one element. So we can keep a running total pre and simply add nums[i] as we advance, avoiding repeated summation.

For the suffix minimum, the challenge is that the suffix shrinks from the left as i increases, so we cannot easily update it on the fly while moving left to right. Instead, we precompute it by traversing the array from back to front. Since suffixMin over the range [i, n - 1] is just the smaller of nums[i] and the minimum over [i + 1, n - 1], we can build an array suf where suf[i] = min(nums[i], suf[i + 1]). This lets us look up the suffix minimum for any starting position in constant time.

Once we have the precomputed suf array and a running prefix sum pre, we can sweep through each split index i (from 0 to n - 2), compute pre - suf[i + 1], and track the maximum value seen. This reduces the problem to a single linear pass after the preprocessing step, giving an efficient O(n) solution.

Pattern Learn more about Prefix Sum patterns.

Solution Approach

Solution 1: Prefix Sum + Enumeration

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.

Concretely, we initialize every entry of suf with the last element nums[-1], then iterate i from n - 2 down to 0, setting suf[i] = min(nums[i], suf[i + 1]). After this pass, suf[i + 1] directly gives us suffixMin(i) for any split index i.

Next, we define a variable pre to represent the prefix sum of the array nums, initialized to 0. We traverse the first n - 1 elements of the array nums. For each index i, we add nums[i] to pre, so that pre now equals prefixSum(i). Then we calculate the split score score(i) = pre - suf[i + 1]. We use a variable ans, initialized to negative infinity, to maintain the maximum value among all split scores.

Finally, we return ans as the answer.

The time complexity is O(n), where n is the length of the array nums, since we perform one backward pass to build suf and one forward pass to compute the scores. The space complexity is O(n) due to the additional suf array.

Example Walkthrough

Let's trace through the solution with a small example: nums = [3, 1, 5, 2, 4], where n = 5.

Step 1: Build the suffix minimum array suf

We initialize every entry with the last element nums[4] = 4, then iterate from i = 3 down to i = 0, setting suf[i] = min(nums[i], suf[i + 1]).

i	nums[i]	suf[i + 1]	suf[i] = min(nums[i], suf[i+1])
4	4	—	4 (initialized)
3	2	4	min(2, 4) = 2
2	5	2	min(5, 2) = 2
1	1	2	min(1, 2) = 1
0	3	1	min(3, 1) = 1

So the final suf array is:

suf = [1, 1, 2, 2, 4]

This means, for example, suf[2] = 2 is the minimum of nums[2..4] = [5, 2, 4], which is indeed 2.

Step 2: Sweep through split indices, accumulating the prefix sum

We initialize pre = 0 and ans = -∞. We iterate i from 0 to n - 2 = 3. At each step we add nums[i] to pre (so pre = prefixSum(i)), then compute score(i) = pre - suf[i + 1].

i	nums[i]	pre (prefixSum)	suf[i + 1] (suffixMin)	score(i) = pre - suf[i+1]	ans (running max)
0	3	3	suf[1] = 1	3 - 1 = 2	2
1	1	4	suf[2] = 2	4 - 2 = 2	2
2	5	9	suf[3] = 2	9 - 2 = 7	7
3	2	11	suf[4] = 4	11 - 4 = 7	7

Step 3: Return the result

The maximum score across all valid split indices is ans = 7.

Verification: The best splits occur at i = 2 and i = 3. For i = 2, the prefix is [3, 1, 5] with sum 9, and the suffix is [2, 4] with minimum 2, giving 9 - 2 = 7. This confirms the result. ✅

Solution Implementation

1from typing import List
2from math import inf
3
4
5class Solution:
6    def maximumScore(self, nums: List[int]) -> int:
7        n = len(nums)
8
9        # suffix_min[i] holds the minimum value among nums[i:]
10        # Initialize every entry with the last element as the default.
11        suffix_min = [nums[-1]] * n
12
13        # Fill the suffix minimum array from right to left.
14        # suffix_min[i] is the smaller of the current value and the
15        # minimum of everything to its right.
16        for i in range(n - 2, -1, -1):
17            suffix_min[i] = min(nums[i], suffix_min[i + 1])
18
19        best_score = -inf  # Track the maximum score found so far.
20        prefix_sum = 0      # Running sum of nums[0..i].
21
22        # For each split point i, the left part is nums[0..i] (its sum is
23        # prefix_sum) and the right part starts at i + 1 (its minimum is
24        # suffix_min[i + 1]). The score is the left sum minus the right min.
25        for i in range(n - 1):
26            prefix_sum += nums[i]
27            best_score = max(best_score, prefix_sum - suffix_min[i + 1])
28
29        return best_score
30

1class Solution {
2    public long maximumScore(int[] nums) {
3        int n = nums.length;
4
5        // suffixMin[i] holds the minimum value among nums[i..n-1]
6        long[] suffixMin = new long[n];
7        suffixMin[n - 1] = nums[n - 1];
8        for (int i = n - 2; i >= 0; --i) {
9            suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
10        }
11
12        // Track the best score found so far
13        long maxScore = Long.MIN_VALUE;
14
15        // Accumulate the prefix sum as we move from left to right
16        long prefixSum = 0;
17        for (int i = 0; i < n - 1; ++i) {
18            prefixSum += nums[i];
19            // Score = sum of the prefix minus the minimum value in the remaining suffix
20            maxScore = Math.max(maxScore, prefixSum - suffixMin[i + 1]);
21        }
22
23        return maxScore;
24    }
25}
26

1class Solution {
2public:
3    long long maximumScore(vector<int>& nums) {
4        int n = nums.size();
5
6        // suffixMin[i] holds the minimum value among nums[i..n-1]
7        vector<long long> suffixMin(n);
8        suffixMin[n - 1] = nums[n - 1];
9        for (int i = n - 2; i >= 0; --i) {
10            suffixMin[i] = min(static_cast<long long>(nums[i]), suffixMin[i + 1]);
11        }
12
13        long long answer = LLONG_MIN;  // best score found so far
14        long long prefixSum = 0;       // running sum of nums[0..i]
15
16        // Try every split point: prefix ends at i, suffix starts at i+1
17        for (int i = 0; i < n - 1; ++i) {
18            prefixSum += nums[i];
19            // Score = sum of the prefix minus the minimum of the remaining suffix
20            answer = max(answer, prefixSum - suffixMin[i + 1]);
21        }
22
23        return answer;
24    }
25};
26

1function maximumScore(nums: number[]): number {
2    const length = nums.length;
3
4    // suffixMin[i] holds the minimum value among nums[i..length-1]
5    const suffixMin: number[] = new Array(length);
6    suffixMin[length - 1] = nums[length - 1];
7    for (let i = length - 2; i >= 0; --i) {
8        suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
9    }
10
11    // Track the maximum score found across all split points
12    let answer = Number.NEGATIVE_INFINITY;
13
14    // prefixSum accumulates the sum of nums[0..i]
15    let prefixSum = 0;
16    for (let i = 0; i < length - 1; ++i) {
17        prefixSum += nums[i];
18        // Score = (sum of prefix) - (minimum of the remaining suffix)
19        answer = Math.max(answer, prefixSum - suffixMin[i + 1]);
20    }
21
22    return answer;
23}
24

Time and Space Complexity

Time complexity: O(n). Here, n is the length of the array nums. Building the suffix minimum array suf requires iterating through the array once in O(n), and the subsequent loop that accumulates the prefix sum pre and updates the answer ans also runs in O(n). Therefore, the overall time complexity is O(n).
Space complexity: O(n). The suffix minimum array suf stores n elements, requiring O(n) extra space. The remaining variables (pre, ans, i, etc.) use only O(1) space. Hence, the overall space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing `suffixMin(i)` with the wrong index in the `suffix_min` array

The most frequent mistake is mixing up which suffix the minimum should cover. By definition, suffixMin(i) is the minimum over nums[i + 1 ... n - 1] (the part after the split), not including nums[i]. A careless implementation often writes suffix_min[i] instead of suffix_min[i + 1]:

# WRONG: this includes nums[i] in the suffix, which belongs to the prefix.
best_score = max(best_score, prefix_sum - suffix_min[i])

Solution: Always use suffix_min[i + 1] when scoring split index i, because the suffix starts at index i + 1. Since the loop runs i from 0 to n - 2, i + 1 ranges from 1 to n - 1, so the access is always in bounds.

for i in range(n - 1):
    prefix_sum += nums[i]
    best_score = max(best_score, prefix_sum - suffix_min[i + 1])

Pitfall 2: Iterating over all `n` indices instead of `n - 1`

If you loop for i in range(n), then at i = n - 1 the suffix nums[n ...] is empty, and accessing suffix_min[n] causes an IndexError. The problem explicitly requires a non-empty suffix (0 <= i < n - 1).

Solution: Restrict the split loop to range(n - 1) so the suffix is never empty.

Pitfall 3: Initializing `best_score` to `0` instead of negative infinity

A common bug is initializing the answer to 0. Since the array may contain negative numbers, the maximum score can legitimately be negative. Starting at 0 would incorrectly clamp the result.

# WRONG: assumes the best score is at least 0.
best_score = 0

Solution: Initialize best_score = -inf (or to the first computed score) so that genuinely negative maximum scores are reported correctly.

Pitfall 4: Mishandling arrays of length less than 2

The split requires both a non-empty prefix and a non-empty suffix, so n must be at least 2. With n < 2 there is no valid split index. Additionally, the line suffix_min = [nums[-1]] * n will raise an IndexError on an empty array.

Solution: Guard against small inputs explicitly if such cases are possible:

if n < 2:
    return -inf  # or raise an error / return a sentinel, per problem contract

Pitfall 5: Recomputing the suffix minimum naively inside the loop

Computing min(nums[i + 1:]) on each iteration turns the algorithm into O(n²), which can time out on large inputs.

Solution: Precompute the suffix_min array in a single backward pass (O(n)), then look up the value in O(1) during the forward scan, keeping the overall complexity at O(n).

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering