2219. Maximum Sum Score of Array (Leetcode Medium)
Maximum Sum Score of Array - Video Solution
Watch 3 video solutions for Maximum Sum Score of Array, a medium level problem involving Array, Prefix Sum. This walkthrough by Programming Live with Larry has 174 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a 0-indexed integer array nums of length n.
The sum score of nums at an index i where 0 <= i < n is the maximum of:
- The sum of the first
i + 1elements ofnums. - The sum of the last
n - ielements ofnums.
Return the maximum sum score of nums at any index.
Example 1:
Input: nums = [4,3,-2,5] Output: 10 Explanation: The sum score at index 0 is max(4, 4 + 3 + -2 + 5) = max(4, 10) = 10. The sum score at index 1 is max(4 + 3, 3 + -2 + 5) = max(7, 6) = 7. The sum score at index 2 is max(4 + 3 + -2, -2 + 5) = max(5, 3) = 5. The sum score at index 3 is max(4 + 3 + -2 + 5, 5) = max(10, 5) = 10. The maximum sum score of nums is 10.
Example 2:
Input: nums = [-3,-5] Output: -3 Explanation: The sum score at index 0 is max(-3, -3 + -5) = max(-3, -8) = -3. The sum score at index 1 is max(-3 + -5, -5) = max(-8, -5) = -5. The maximum sum score of nums is -3.
Constraints:
n == nums.length1 <= n <= 105-105 <= nums[i] <= 105
Approach Overview
Problem Overview: You are given an integer array nums. For every index i, calculate a score defined as the larger value between the prefix sum nums[0..i] and the suffix sum nums[i..n-1]. The goal is to return the maximum score among all indices.
Approach 1: Brute Force Prefix/Suffix Calculation (O(n²) time, O(1) space)
The direct approach recomputes sums for every index. For each i, iterate from the start of the array to compute the prefix sum and iterate from i to the end to compute the suffix sum. Take max(prefix, suffix) as the score for that index and keep track of the best value. This approach uses only simple iteration over the array, but repeated summation makes it inefficient for large inputs.
Approach 2: Prefix Sum + Total Sum (O(n) time, O(n) space)
Precompute prefix sums using a prefix sum array. Let prefix[i] represent the sum of elements from 0 to i. The suffix sum starting at i can be derived from the total array sum as total - prefix[i-1]. Iterate through the array once more and compute the score at each index as max(prefix[i], suffix[i]). This removes redundant summation and keeps all operations constant time per index.
Approach 3: Running Prefix with Derived Suffix (O(n) time, O(1) space)
The optimal solution avoids storing a full prefix array. First compute the total sum of the array. Then iterate once while maintaining a running prefix sum. At index i, the prefix sum is the accumulated value so far and the suffix sum is total - prefix_before_i. Compute the score using max(prefix, suffix) and update the global maximum. This approach uses constant extra memory and a single pass after computing the total.
Recommended for interviews: The running prefix sum approach is the expected solution. Interviewers want to see recognition of the prefix–suffix relationship and the ability to derive suffix sums from the total sum. Starting with the brute force explanation shows problem understanding, but optimizing with prefix sums demonstrates algorithmic maturity.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix and Suffix Recalculation | O(n²) | O(1) | Useful for understanding the scoring definition or verifying small test cases |
| Prefix Sum Array | O(n) | O(n) | Good when prefix values are reused multiple times or needed for debugging |
| Running Prefix with Total Sum (Optimal) | O(n) | O(1) | Best general solution with minimal memory usage |