2219. Maximum Sum Score of Array 🔒
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 firsti + 1
elements) - The sum of elements from index
i
to the end of the array (the lastn - 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).
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 traverser
(right sum) starts with the total sum of all elements
As we iterate through each element x
:
- We add
x
tol
(nowl
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
andr
as potential maximum values - Then we subtract
x
fromr
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
withl += x
. Nowl
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
andr
. Update the answer withans = 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
withr -= x
. This preparesr
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 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
- Prefix sum (start to index 0):
- 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
- Prefix sum (start to index 1):
- 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
- Prefix sum (start to index 2):
- 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 takesO(n)
time to compute the sum of all elements - The for loop iterates through each element in
nums
exactly once, performingO(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
andr
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.
Which of the following is a good use case for backtracking?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!