Skip to content

2219. Maximum Sum Score of Array πŸ”’

Description

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.

 

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.length
  • 1 <= n <= 105
  • -105 <= nums[i] <= 105

Solutions

Solution 1: Prefix Sum

Thinking

The score at \(i\) is the larger of the prefix sum through \(i\) and the suffix sum through \(i\); we want the maximum over \(i\). \(n \le 10^5\) forbids summing from scratch at each index.

Both sums can be kept while scanning: start with total \(r\), add \(x\) into prefix \(l\), update the answer by \(\max(l, r)\), then subtract \(x\) from \(r\). One pass suffices.

We can use two variables \(l\) and \(r\) to represent the prefix sum and suffix sum of the array, respectively. Initially, \(l = 0\) and \(r = \sum_{i=0}^{n-1} \textit{nums}[i]\).

Next, we traverse the array \(\textit{nums}\). For each element \(x\), we add \(x\) to \(l\) and update the answer \(\textit{ans} = \max(\textit{ans}, l, r)\), then subtract \(x\) from \(r\).

After the traversal, return the answer \(\textit{ans}\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public long maximumSumScore(int[] nums) {
        long l = 0, r = 0;
        for (int x : nums) {
            r += x;
        }
        long ans = Long.MIN_VALUE;
        for (int x : nums) {
            l += x;
            ans = Math.max(ans, Math.max(l, r));
            r -= x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    long long maximumSumScore(vector<int>& nums) {
        long long l = 0, r = accumulate(nums.begin(), nums.end(), 0LL);
        long long ans = -1e18;
        for (int x : nums) {
            l += x;
            ans = max({ans, l, r});
            r -= x;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func maximumSumScore(nums []int) int64 {
    l, r := 0, 0
    for _, x := range nums {
        r += x
    }
    ans := math.MinInt64
    for _, x := range nums {
        l += x
        ans = max(ans, max(l, r))
        r -= x
    }
    return int64(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function maximumSumScore(nums: number[]): number {
    let l = 0;
    let r = nums.reduce((a, b) => a + b, 0);
    let ans = -Infinity;
    for (const x of nums) {
        l += x;
        ans = Math.max(ans, l, r);
        r -= x;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn maximum_sum_score(nums: Vec<i32>) -> i64 {
        let mut l = 0;
        let mut r: i64 = nums.iter().map(|&x| x as i64).sum();
        let mut ans = std::i64::MIN;
        for &x in &nums {
            l += x as i64;
            ans = ans.max(l).max(r);
            r -= x as i64;
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumSumScore = function (nums) {
    let l = 0;
    let r = nums.reduce((a, b) => a + b, 0);
    let ans = -Infinity;
    for (const x of nums) {
        l += x;
        ans = Math.max(ans, l, r);
        r -= x;
    }
    return ans;
};

Comments