We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Sum Score of Array

Number: 2369

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given a 0-indexed integer array nums, the sum score at an index i is defined as the maximum between the sum of the first i+1 elements and the sum of the last n-i elements. The goal is to return the maximum sum score among all indices.

Key Insights

  • The score at index i is determined by two sums: the prefix sum (from index 0 to i) and the suffix sum (from index i to the end).
  • Instead of precomputing both prefix and suffix sums separately, you can compute the total sum first and then update the prefix sum in one pass.
  • The suffix sum for the current index can be computed as: suffix = total_sum - (prefix sum computed till the previous index).
  • The problem can be solved in a single pass after determining the total sum.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution first computes the total sum of the array. Then, iterate through the array, maintaining a running prefix sum. For each index, compute the suffix sum as:
  suffix = total_sum - (prefix sum before adding the current element)
Alternatively, after updating the prefix sum, note that:
  suffix = total_sum - prefix + current element
Finally, determine the maximum score by taking the maximum of the prefix and the computed suffix. This approach uses a single pass (after computing the total sum) and constant extra space.

Code Solutions

# Python solution with detailed comments

def maximumSumScore(nums):
    # Calculate the total sum of the array
    total_sum = sum(nums)
    max_score = float('-inf')  # Initialize max score with very small number
    prefix_sum = 0            # Initialize prefix sum

    # Loop through each element in the array
    for num in nums:
        prefix_sum += num                  # Update the prefix sum to include current element
        # Calculate suffix sum by subtracting the sum before the current element:
        # suffix = total_sum - (prefix_sum - num) which simplifies to:
        suffix_sum = total_sum - prefix_sum + num
        # The score at this index is the maximum of prefix_sum and suffix_sum
        current_score = max(prefix_sum, suffix_sum)
        # Update the maximum score found
        max_score = max(max_score, current_score)
    return max_score

# Example usage:
# nums = [4, 3, -2, 5]
# print(maximumSumScore(nums))
← Back to All Questions