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 171 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i + 1 elements of nums.n - i elements of nums.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] <= 105Problem 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.
| 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 |