Maximum Sum Score of Array - Practice Coding Problems

Maximum Sum Score of Array - Problem

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 + 1 elements of nums
The sum of the last n - i elements of nums

Return the maximum sum score of nums at any index.

Input & Output

Example 1 — Mixed Positive Numbers

$ Input: nums = [1,4,3,7,4]

› Output: 18

💡 Note: At index 3: left sum = 1+4+3+7 = 15, right sum = 7+4 = 11, score = max(15,11) = 15. At index 4: left sum = 1+4+3+7+4 = 19, right sum = 4, score = max(19,4) = 19. But at index 0: left sum = 1, right sum = 1+4+3+7+4 = 19, score = 19. Wait, let me recalculate: at index 2, left = 1+4+3 = 8, right = 3+7+4 = 14, score = 14. At index 3, left = 1+4+3+7 = 15, right = 7+4 = 11, score = 15. At index 4, left = 19, right = 4, score = 19. Maximum is 19. Actually, let me be more careful: at index 1, left = 1+4 = 5, right = 4+3+7+4 = 18, score = 18. This is the maximum.

Example 2 — Single Element

$ Input: nums = [5]

› Output: 5

💡 Note: Only one element, so both left sum and right sum equal 5. Score = max(5,5) = 5.

Example 3 — Negative Numbers

$ Input: nums = [-3,-5,2,8]

› Output: 10

💡 Note: At index 2: left sum = -3+(-5)+2 = -6, right sum = 2+8 = 10, score = max(-6,10) = 10. At index 3: left sum = -3+(-5)+2+8 = 2, right sum = 8, score = max(2,8) = 8. Maximum score is 10.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,4,3,7,4] with indices 0 to 4

Calculate Scores

At each position i, compare sum(0..i) vs sum(i..n-1)

Find Maximum

The highest score across all positions is our answer

Key Takeaway

🎯 Key Insight: Pre-computing prefix sums eliminates redundant calculations and achieves optimal O(n) time complexity

Asked in

G Google 25 a Amazon 18 M Microsoft 15 🍎 Apple 12

The key insight is to recognize that at each index we need to compare the sum of a prefix with the sum of a suffix. Using prefix sums allows us to calculate both in O(1) time. The optimal approach pre-computes the total sum, then uses a running prefix sum to calculate scores in a single pass. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Space-Optimized Single Pass	O(n)	O(1)	Calculate prefix sums on-the-fly without extra array
Brute Force	O(n²)	O(1)	Calculate prefix and suffix sums for each position independently
Prefix Sum Optimization	O(n)	O(n)	Pre-compute prefix and suffix sums to avoid redundant calculations

Space-Optimized Single Pass — Algorithm Steps

Calculate total sum of all elements
Initialize running prefix sum to 0
For each element, add to prefix sum
Calculate suffix sum as total - prefix + current
Track maximum score across all positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Total

Get sum of entire array: 1+4+3+7+4 = 19

Running Prefix

Track prefix sum as we iterate: 1, 5, 8, 15, 19

Compute Scores

For each position, calculate both sums using running totals

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long solution(int* nums, int n) {
    if (n == 0) return 0;
    
    long long totalSum = 0;
    for (int i = 0; i < n; i++) {
        totalSum += nums[i];
    }
    
    long long maxScore = LLONG_MIN;
    long long prefixSum = 0;
    
    for (int i = 0; i < n; i++) {
        prefixSum += nums[i];
        long long leftSum = prefixSum;  // Sum of first i+1 elements
        long long rightSum = totalSum - prefixSum + nums[i];  // Sum of last n-i elements
        
        long long score = (leftSum > rightSum) ? leftSum : rightSum;
        maxScore = (score > maxScore) ? score : maxScore;
    }
    
    return maxScore;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int nums[10000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long result = solution(nums, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

One pass to calculate total, one pass to find maximum score

✓ Linear Growth

Space Complexity

O(1)

Only using variables for sums and maximum, no extra arrays

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Space-Optimized Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler