LeetCode 2219 - Maximum Sum Score of Array

The problem gives us a 0-indexed integer array nums of length n and asks us to compute the maximum sum score among all indices of the array.

leetcodemediumarrayprefix-sum

LeetCode Problem 2219

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem gives us a 0-indexed integer array nums of length n and asks us to compute the maximum sum score among all indices of the array. The sum score at index i is defined as the maximum of two sums: the sum of the first i + 1 elements of the array (the prefix sum up to index i) and the sum of the last n - i elements (the suffix sum starting at index i).

In simpler terms, for every position in the array, we look at the total sum if we consider everything from the start up to that index and everything from that index to the end. The sum score is the bigger of the two. We then want the largest sum score across all indices.

Constraints indicate that the array can be quite large (1 <= n <= 10^5) and numbers can be negative or positive within a range of -10^5 to 10^5. This rules out any brute-force solution that computes sums repeatedly in a nested manner, because it would be too slow for the upper limit.

Important edge cases include arrays of length 1, arrays where all elements are negative, and arrays where the maximum sum score comes from either the prefix or suffix rather than the whole array.

Approaches

Brute Force: The naive approach would be to iterate over every index i, compute the sum of the first i + 1 elements and the sum of the last n - i elements separately, take the maximum, and track the overall maximum. While correct, this approach is inefficient because computing sums for each index separately leads to repeated work, resulting in an O(n^2) time complexity for arrays of size n.

Optimal Approach: The key insight is that we can precompute prefix sums and suffix sums in O(n) time. Once we have these cumulative sums, computing the sum score for any index i reduces to a single comparison of two numbers: prefix[i] and suffix[i]. This allows us to iterate over the array once to compute the maximum sum score, achieving an O(n) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Compute sums for each index separately
Optimal O(n) O(n) Precompute prefix and suffix sums, then compute max sum score

Algorithm Walkthrough

  1. Initialize two arrays prefix and suffix of length n. prefix[i] will store the sum of the first i + 1 elements, and suffix[i] will store the sum of the last n - i elements.
  2. Compute the prefix sums: start with prefix[0] = nums[0] and for each subsequent index i, set prefix[i] = prefix[i-1] + nums[i].
  3. Compute the suffix sums: start with suffix[n-1] = nums[n-1] and for each previous index i from n-2 down to 0, set suffix[i] = suffix[i+1] + nums[i].
  4. Initialize a variable max_score to negative infinity to track the maximum sum score.
  5. Iterate over each index i from 0 to n-1, compute score = max(prefix[i], suffix[i]), and update max_score if score is larger.
  6. Return max_score after the loop completes.

Why it works: By precomputing prefix and suffix sums, we eliminate repeated sum calculations. The algorithm guarantees that we compare the correct prefix and suffix sums for each index, ensuring that the maximum sum score is found. Each array is only traversed a constant number of times, maintaining linear time complexity.

Python Solution

from typing import List

class Solution:
    def maximumSumScore(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * n
        suffix = [0] * n
        
        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = prefix[i-1] + nums[i]
        
        suffix[n-1] = nums[n-1]
        for i in range(n-2, -1, -1):
            suffix[i] = suffix[i+1] + nums[i]
        
        max_score = float('-inf')
        for i in range(n):
            max_score = max(max_score, max(prefix[i], suffix[i]))
        
        return max_score

Implementation Notes: The code first computes prefix and suffix sums in separate loops, which allows constant-time access to any index's sum. The final loop computes the sum score at each index efficiently. Using float('-inf') ensures that negative-only arrays are handled correctly.

Go Solution

func maximumSumScore(nums []int) int64 {
    n := len(nums)
    prefix := make([]int64, n)
    suffix := make([]int64, n)
    
    prefix[0] = int64(nums[0])
    for i := 1; i < n; i++ {
        prefix[i] = prefix[i-1] + int64(nums[i])
    }
    
    suffix[n-1] = int64(nums[n-1])
    for i := n-2; i >= 0; i-- {
        suffix[i] = suffix[i+1] + int64(nums[i])
    }
    
    maxScore := prefix[0]
    for i := 0; i < n; i++ {
        if prefix[i] > suffix[i] && prefix[i] > maxScore {
            maxScore = prefix[i]
        } else if suffix[i] >= prefix[i] && suffix[i] > maxScore {
            maxScore = suffix[i]
        }
    }
    
    return maxScore
}

Go-specific Notes: We use int64 to prevent integer overflow, since sums can exceed the int range. The logic is identical to Python, but Go requires explicit type conversions when summing integers.

Worked Examples

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

i prefix[i] suffix[i] max(prefix, suffix)
0 4 10 10
1 7 6 7
2 5 3 5
3 10 5 10

Maximum sum score is 10.

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

i prefix[i] suffix[i] max(prefix, suffix)
0 -3 -8 -3
1 -8 -5 -5

Maximum sum score is -3.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Prefix sums, suffix sums, and max score calculation each take O(n) time
Space O(n) We store prefix and suffix arrays of length n

Using prefix and suffix arrays ensures linear time without redundant computation. Space usage is linear but can be reduced to O(1) if we reuse the input array or compute suffix sum on the fly.

Test Cases

# Provided examples
assert Solution().maximumSumScore([4,3,-2,5]) == 10  # mix of positive and negative numbers
assert Solution().maximumSumScore([-3,-5]) == -3     # all negative numbers

# Edge cases
assert Solution().maximumSumScore([5]) == 5          # single element
assert Solution().maximumSumScore([1,2,3,4,5]) == 15 # increasing positive numbers
assert Solution().maximumSumScore([-1,-2,-3,-4]) == -1 # decreasing negative numbers
assert Solution().maximumSumScore([0,0,0]) == 0      # all zeros
assert Solution().maximumSumScore([10,-1,-1,-1,10]) == 17 # maximum sum not at ends
Test Why
[4,3,-2,5] Mix of positive and negative numbers
[-3,-5] All negative numbers
[5] Single-element array
[1,2,3,4,5] Increasing sequence
[-1,-2,-3,-4] Decreasing negative numbers
[0,0,0] All zeros
[10,-1,-1,-1,10] Maximum sum not at ends

Edge Cases

Single-element array: With only one element, the prefix and suffix sums are the same. Our solution handles this correctly because the prefix and suffix arrays are initialized with the element itself.

All negative numbers: A naive implementation might initialize max_score to zero, incorrectly returning a non-existent positive sum. Using negative infinity ensures we capture the largest negative value.

Maximum sum at ends: Sometimes the maximum sum score occurs at the first or last index. The algorithm correctly considers both ends because prefix sums start from the left and suffix sums start from the right.

This completes a robust, detailed solution guide for LeetCode 2219.