How hard is LeetCode 2219. Maximum Sum Score of Array?

LeetCode 2219. Maximum Sum Score of Array is rated Medium on LeetCode.

What is the time complexity of LeetCode 2219. Maximum Sum Score of Array?

The Python solution on this page runs in O(n), where n is the length of the array \textit{nums}.

What is the space complexity of LeetCode 2219. Maximum Sum Score of Array?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2219. Maximum Sum Score of Array cover?

LeetCode 2219. Maximum Sum Score of Array is tagged Array and Prefix Sum on LeetCode.

Is LeetCode 2219. Maximum Sum Score of Array a premium problem?

Yes. LeetCode 2219. Maximum Sum Score of Array is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Maximum Sum Score of Array — LeetCode 2219 Python Solution

MediumLeetCode PremiumArrayPrefix Sum

Problem: #2219
Pattern: Prefix Sum
Reading time: 2 min
Source: leetcode.com

The 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.

Example

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.

Python solution

Python

class Solution:
    def maximumSumScore(self, nums: List[int]) -> int:
        l, r = 0, sum(nums)
        ans = -inf
        for x in nums:
            l += x
            ans = max(ans, l, r)
            r -= x
        return ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array \textit{nums}
Space	O(1) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2219. Maximum Sum Score of Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2219. Maximum Sum Score of Array?: LeetCode 2219. Maximum Sum Score of Array is rated Medium on LeetCode.
What is the time complexity of LeetCode 2219. Maximum Sum Score of Array?: The Python solution on this page runs in O(n), where n is the length of the array \textit{nums}.
What is the space complexity of LeetCode 2219. Maximum Sum Score of Array?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2219. Maximum Sum Score of Array cover?: LeetCode 2219. Maximum Sum Score of Array is tagged Array and Prefix Sum on LeetCode.
Is LeetCode 2219. Maximum Sum Score of Array a premium problem?: Yes. LeetCode 2219. Maximum Sum Score of Array is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.