LeetCode 3788 - Maximum Score of a Split

The problem asks us to maximize a "score" obtained by splitting an integer array nums at a valid index i. For each split index i, the score is calculated as the sum of all elements from the beginning of the array up to i (prefixSum) minus the minimum value in the remaining…

leetcodemediumarrayprefix-sum

LeetCode Problem 3788

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem asks us to maximize a "score" obtained by splitting an integer array nums at a valid index i. For each split index i, the score is calculated as the sum of all elements from the beginning of the array up to i (prefixSum) minus the minimum value in the remaining elements (suffixMin). The input array nums can have both positive and negative integers, with length ranging from 2 up to 10^5, and elements potentially as large as ±10^9.

In simpler terms, the problem is about choosing a split point so that the sum of the first part of the array is maximized relative to the minimum of the second part. The result is a single integer representing the maximum score possible among all valid splits. Important observations include handling negative numbers correctly, as both prefix sums and suffix minimums can be negative, which affects the subtraction.

Edge cases to watch out for include arrays of length 2, arrays with all negative numbers, arrays with uniform values, and splits where the minimum in the suffix is at the very end of the array. The problem guarantees at least two elements, so there will always be at least one valid split.

Approaches

The brute-force approach iterates through each possible split index i, calculates the prefix sum up to i, then scans the suffix from i+1 to the end to find the minimum. The score is computed as prefixSum(i) - suffixMin(i), and the maximum score is tracked. While correct, this method is inefficient because for each of the n-1 split points, finding the suffix minimum requires O(n) operations, resulting in a total time complexity of O(n^2), which is too slow for n up to 10^5.

The optimal approach uses precomputation to reduce the cost of repeated calculations. First, compute prefix sums in one pass, storing them in an array. Then, compute the suffix minimums from right to left in a separate pass. With these two arrays ready, the score for each split can be computed in O(1) time. This reduces the total time complexity to O(n), which is feasible for the given constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Computes prefix sum and suffix min for each split without precomputation
Optimal O(n) O(n) Precompute prefix sums and suffix minimums for constant-time score calculation

Algorithm Walkthrough

  1. Initialize an array prefix of length n to store prefix sums. Set prefix[0] to nums[0].
  2. Loop from index 1 to n-1 and compute prefix[i] = prefix[i-1] + nums[i]. This gives cumulative sums for the left part of every split.
  3. Initialize an array suffixMin of length n to store suffix minimums. Set suffixMin[n-1] to nums[n-1].
  4. Loop backward from n-2 to 0, updating suffixMin[i] = min(nums[i], suffixMin[i+1]). This ensures each index stores the minimum of the suffix starting at that index.
  5. Initialize a variable maxScore to negative infinity to track the maximum score found.
  6. Loop through split indices i from 0 to n-2, compute score = prefix[i] - suffixMin[i+1], and update maxScore if score is greater.
  7. Return maxScore.

Why it works: By precomputing the prefix sums and suffix minimums, each split's score can be computed in constant time. This ensures that we correctly consider all possible splits while avoiding repeated calculations. The arrays maintain the invariant that prefix[i] contains the sum up to i and suffixMin[i] contains the minimum from i to the end, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def maximumScore(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * n
        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = prefix[i-1] + nums[i]

        suffixMin = [0] * n
        suffixMin[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            suffixMin[i] = min(nums[i], suffixMin[i+1])

        maxScore = float('-inf')
        for i in range(n-1):
            score = prefix[i] - suffixMin[i+1]
            if score > maxScore:
                maxScore = score

        return maxScore

This Python implementation first builds the prefix array to store cumulative sums and the suffixMin array for suffix minimums. The final loop efficiently computes the score for each split using these arrays, tracking the maximum value found. Using float('-inf') ensures that negative scores are correctly considered.

Go Solution

func maximumScore(nums []int) int64 {
    n := len(nums)
    prefix := make([]int64, n)
    prefix[0] = int64(nums[0])
    for i := 1; i < n; i++ {
        prefix[i] = prefix[i-1] + int64(nums[i])
    }

    suffixMin := make([]int64, n)
    suffixMin[n-1] = int64(nums[n-1])
    for i := n-2; i >= 0; i-- {
        if int64(nums[i]) < suffixMin[i+1] {
            suffixMin[i] = int64(nums[i])
        } else {
            suffixMin[i] = suffixMin[i+1]
        }
    }

    maxScore := int64(-1 << 63)
    for i := 0; i < n-1; i++ {
        score := prefix[i] - suffixMin[i+1]
        if score > maxScore {
            maxScore = score
        }
    }

    return maxScore
}

In Go, integer overflow is considered by using int64 for cumulative sums and calculations. Arrays are dynamically allocated using make, and the comparison logic ensures that the suffix minimum is correctly computed. The algorithm structure mirrors the Python version.

Worked Examples

Example 1: nums = [10, -1, 3, -4, -5]

i prefix[i] suffixMin[i+1] score
0 10 -5 15
1 9 -5 14
2 12 -5 17
3 8 -5 13

Maximum score is 17 at i = 2.

Example 2: nums = [-7, -5, 3]

i prefix[i] suffixMin[i+1] score
0 -7 -5 -2
1 -12 3 -15

Maximum score is -2 at i = 0.

Example 3: nums = [1, 1]

i prefix[i] suffixMin[i+1] score
0 1 1 0

Maximum score is 0 at i = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass for prefix sums, one pass for suffix minimums, one pass for computing scores
Space O(n) Storing prefix sums and suffix minimum arrays

The approach is linear in both time and space because each element is visited a constant number of times and two arrays of length n are allocated.

Test Cases

# Example test cases
assert Solution().maximumScore([10, -1, 3, -4, -5]) == 17  # Example 1
assert Solution().maximumScore([-7, -5, 3]) == -2          # Example 2
assert Solution().maximumScore([1, 1]) == 0               # Example 3

# Boundary and stress test cases
assert Solution().maximumScore([0, 0]) == 0               # minimal values
assert Solution().maximumScore([-1, -2]) == 1            # negative numbers
assert Solution().maximumScore([1, 2, 3, 4, 5]) == 14    # increasing sequence
assert Solution().maximumScore([5, 4, 3, 2, 1]) == 14    # decreasing sequence
assert Solution().maximumScore([1000000000, -1000000000]) == 2000000000  # large numbers
Test Why
[10, -1, 3, -4, -5] Tests mixed positive and negative numbers, optimal split in the middle
[-7, -5, 3] Tests negative prefix and positive suffix, split at start
[1, 1] Minimal length array, only one split possible
[0, 0] Edge case with zeros
[-1, -2]