2219. Maximum Sum Score of Array 🔒

MediumArrayPrefix Sum

Leetcode Link

Problem Description

You have an array nums with indices from 0 to n-1.

For each index i in the array, you can calculate a "sum score" which is the maximum of two values:

The sum of elements from the start of the array up to and including index i (the first i + 1 elements)
The sum of elements from index i to the end of the array (the last n - i elements)

Your task is to find the maximum sum score among all possible indices in the array.

For example, if nums = [4, 3, -2, 5]:

At index 0: sum score = max(4, 4+3+(-2)+5) = max(4, 10) = 10
At index 1: sum score = max(4+3, 3+(-2)+5) = max(7, 6) = 7
At index 2: sum score = max(4+3+(-2), (-2)+5) = max(5, 3) = 5
At index 3: sum score = max(4+3+(-2)+5, 5) = max(10, 5) = 10

The maximum sum score would be 10.

Note that at each index, the element at that index is included in both sums being compared (it's the last element of the prefix sum and the first element of the suffix sum).

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key observation is that at each index i, we need to compare the sum of elements from start to i (prefix sum) with the sum of elements from i to end (suffix sum).

Instead of recalculating these sums for each index from scratch, we can maintain running totals. Notice that as we move from one index to the next:

The prefix sum grows by including one more element
The suffix sum shrinks by excluding one element

We can track these changes efficiently using two variables:

l (left sum) starts at 0 and accumulates elements as we traverse
r (right sum) starts with the total sum of all elements

As we iterate through each element x:

We add x to l (now l contains the sum up to and including current element)
At this point, r still contains the sum from current element to the end
We can check both l and r as potential maximum values
Then we subtract x from r to prepare for the next iteration

This way, at each position, we have both the prefix sum and suffix sum available without redundant calculations. The time complexity is O(n) since we only traverse the array once, and space complexity is O(1) as we only use a few variables.

The elegance of this approach lies in how the two sums "slide" through the array in opposite directions - one growing from left, one shrinking from right - and at each position, both sums include the current element, which is exactly what the problem requires.

Learn more about Prefix Sum patterns.

Solution Approach

We implement the solution using the prefix sum technique with two pointers that track cumulative sums from both directions.

Initialization:

Set l = 0 to represent the prefix sum (initially empty)
Set r = sum(nums) to represent the suffix sum (initially contains all elements)
Set ans = -inf to track the maximum sum score found

Main Algorithm:

We traverse through each element x in nums:

Update prefix sum: Add the current element to l with l += x. Now l contains the sum from the start up to and including the current element.
Update maximum: Calculate the sum score at the current position by taking the maximum of l and r. Update the answer with ans = max(ans, l, r). At this point:
- l represents the sum of elements from index 0 to current index (inclusive)
- r represents the sum of elements from current index to the end (inclusive)
- Both sums include the current element, which satisfies the problem requirement
Update suffix sum: Subtract the current element from r with r -= x. This prepares r for the next iteration where it will represent the suffix sum starting from the next element.

Example walkthrough with nums = [1, 2, 3]:

Initial: l = 0, r = 6, ans = -inf
Index 0 (x=1): l = 1, ans = max(-inf, 1, 6) = 6, r = 5
Index 1 (x=2): l = 3, ans = max(6, 3, 5) = 6, r = 3
Index 2 (x=3): l = 6, ans = max(6, 6, 3) = 6, r = 0
Return: ans = 6

The algorithm runs in O(n) time complexity with a single pass through the array and uses O(1) extra space for the variables.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with nums = [2, -1, 4]:

Initial Setup:

Calculate total sum: r = 2 + (-1) + 4 = 5
Initialize: l = 0, ans = -inf

Iteration 1 (index 0, x = 2):

Add to prefix: l = 0 + 2 = 2
At this position:
- Prefix sum (start to index 0): l = 2
- Suffix sum (index 0 to end): r = 5
- Sum score = max(2, 5) = 5
Update answer: ans = max(-inf, 2, 5) = 5
Prepare for next: r = 5 - 2 = 3

Iteration 2 (index 1, x = -1):

Add to prefix: l = 2 + (-1) = 1
At this position:
- Prefix sum (start to index 1): l = 1
- Suffix sum (index 1 to end): r = 3
- Sum score = max(1, 3) = 3
Update answer: ans = max(5, 1, 3) = 5
Prepare for next: r = 3 - (-1) = 4

Iteration 3 (index 2, x = 4):

Add to prefix: l = 1 + 4 = 5
At this position:
- Prefix sum (start to index 2): l = 5
- Suffix sum (index 2 to end): r = 4
- Sum score = max(5, 4) = 5
Update answer: ans = max(5, 5, 4) = 5
Prepare for next: r = 4 - 4 = 0

Result: Maximum sum score = 5

The key insight is how l and r maintain the exact sums we need at each position - both including the current element - allowing us to compute each sum score efficiently in constant time.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def maximumSumScore(self, nums: List[int]) -> int:
6        # Initialize left sum as 0 and right sum as total sum of all elements
7        left_sum = 0
8        right_sum = sum(nums)
9      
10        # Initialize the maximum score to negative infinity
11        max_score = -inf
12      
13        # Iterate through each element in the array
14        for num in nums:
15            # Add current element to left sum (include current element in left partition)
16            left_sum += num
17          
18            # Update maximum score by comparing current max with both partition sums
19            # At position i: left_sum includes nums[0] to nums[i]
20            #                right_sum includes nums[i] to nums[n-1]
21            max_score = max(max_score, left_sum, right_sum)
22          
23            # Remove current element from right sum (prepare for next iteration)
24            right_sum -= num
25      
26        # Return the maximum score found
27        return max_score
28

1class Solution {
2    public long maximumSumScore(int[] nums) {
3        // Initialize prefix sum and suffix sum
4        long prefixSum = 0;
5        long suffixSum = 0;
6      
7        // Calculate the total sum (initial suffix sum)
8        for (int num : nums) {
9            suffixSum += num;
10        }
11      
12        // Initialize the maximum score with the smallest possible value
13        long maxScore = Long.MIN_VALUE;
14      
15        // Iterate through each element to find the maximum score
16        for (int num : nums) {
17            // Add current element to prefix sum (prefix includes current element)
18            prefixSum += num;
19          
20            // Update maximum score by comparing with both prefix and suffix sums
21            maxScore = Math.max(maxScore, Math.max(prefixSum, suffixSum));
22          
23            // Remove current element from suffix sum (suffix includes current element before removal)
24            suffixSum -= num;
25        }
26      
27        return maxScore;
28    }
29}
30

1class Solution {
2public:
3    long long maximumSumScore(vector<int>& nums) {
4        // Initialize prefix sum starting from 0
5        long long prefixSum = 0;
6      
7        // Initialize suffix sum with the total sum of all elements
8        long long suffixSum = accumulate(nums.begin(), nums.end(), 0LL);
9      
10        // Initialize the answer with a very small value (negative infinity)
11        long long maxScore = -1e18;
12      
13        // Iterate through each element in the array
14        for (int currentNum : nums) {
15            // Add current element to prefix sum (includes current element)
16            prefixSum += currentNum;
17          
18            // Update maximum score by comparing:
19            // - Current maximum score
20            // - Prefix sum up to and including current element
21            // - Suffix sum starting from current element
22            maxScore = max({maxScore, prefixSum, suffixSum});
23          
24            // Remove current element from suffix sum for next iteration
25            suffixSum -= currentNum;
26        }
27      
28        return maxScore;
29    }
30};
31

1/**
2 * Finds the maximum sum score by calculating prefix and suffix sums
3 * @param nums - Array of numbers to process
4 * @returns The maximum sum score between all prefix and suffix sums
5 */
6function maximumSumScore(nums: number[]): number {
7    // Initialize left sum (prefix sum) starting at 0
8    let leftSum: number = 0;
9  
10    // Initialize right sum (suffix sum) with total sum of all elements
11    let rightSum: number = nums.reduce((accumulator: number, current: number) => accumulator + current, 0);
12  
13    // Track the maximum score found so far
14    let maxScore: number = -Infinity;
15  
16    // Iterate through each element in the array
17    for (const currentNum of nums) {
18        // Add current element to left sum (building prefix sum)
19        leftSum += currentNum;
20      
21        // Update maximum score by comparing current max with both left and right sums
22        maxScore = Math.max(maxScore, leftSum, rightSum);
23      
24        // Remove current element from right sum (reducing suffix sum)
25        rightSum -= currentNum;
26    }
27  
28    return maxScore;
29}
30

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

The initial sum(nums) operation takes O(n) time to compute the sum of all elements
The for loop iterates through each element in nums exactly once, performing O(1) operations in each iteration (addition, subtraction, and max comparisons)
Overall, we have O(n) + O(n) = O(n)

The space complexity is O(1). The algorithm only uses a constant amount of extra space:

Variables l and r store running sums
Variable ans stores the maximum value
Variable x is used in the loop iteration
All these variables use constant space regardless of the input size

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

Common Pitfalls

1. Integer Overflow in Other Languages

While Python handles arbitrary precision integers automatically, implementing this solution in languages like Java or C++ can cause integer overflow when calculating the initial sum or cumulative sums. For arrays with large values, the sum might exceed the maximum value of a 32-bit integer.

Solution: Use 64-bit integers (long in Java, long long in C++) for all sum variables and ensure the return type matches the expected output range.

2. Incorrect Initialization of Maximum Score

A common mistake is initializing max_score to 0 or a small positive number. This fails when all elements in the array are negative, as the maximum score could be negative.

Solution: Always initialize max_score to negative infinity (-inf in Python, INT_MIN or LONG_MIN in other languages) to handle arrays with all negative values correctly.

3. Off-by-One Error in Understanding the Problem

Developers might misinterpret the problem and think that at index i, the element should only be counted in one of the sums (either prefix or suffix), leading to incorrect calculations where they subtract the current element from one of the sums.

Solution: Carefully note that the element at index i is included in BOTH sums being compared. The prefix sum includes elements from index 0 to i (inclusive), and the suffix sum includes elements from index i to n-1 (inclusive).

4. Using Three-Argument max() Incorrectly

In the line max_score = max(max_score, left_sum, right_sum), some might accidentally write max_score = max(left_sum, right_sum), forgetting to compare with the existing maximum score, which would give incorrect results.

Solution: Ensure you're taking the maximum of three values: the current max_score and both partition sums. Alternatively, you can write it as max_score = max(max_score, max(left_sum, right_sum)) for clarity.

5. Handling Single Element Arrays

While the provided solution handles this correctly, some implementations might have edge case issues with single-element arrays where there's only one possible partition.

Solution: Test with edge cases like nums = [5] or nums = [-3] to ensure the solution correctly returns the single element's value as the maximum score.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems