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 _themaximum sum****score of _nums at any index.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6

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 <= 10^5
  • -10^5 <= nums[i] <= 10^5

Solution

Method 1 – Prefix Sum and Suffix Sum

Intuition

To find the maximum sum score at any index, we need to consider the sum of the first i+1 elements and the sum of the last n-i elements for each index. The answer is the maximum among all these values. We can use prefix and suffix sums to compute these efficiently.

Approach

  1. Compute prefix sums for all indices.
  2. Compute suffix sums for all indices.
  3. For each index, calculate the sum score as the maximum of prefix and suffix sum at that index.
  4. Return the maximum sum score found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    long long maximumSumScore(vector<int>& nums) {
        int n = nums.size();
        vector<long long> prefix(n), suffix(n);
        prefix[0] = nums[0];
        for (int i = 1; i < n; ++i) prefix[i] = prefix[i-1] + nums[i];
        suffix[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i) suffix[i] = suffix[i+1] + nums[i];
        long long ans = LLONG_MIN;
        for (int i = 0; i < n; ++i)
            ans = max(ans, max(prefix[i], suffix[i]));
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func maximumSumScore(nums []int) int64 {
    n := len(nums)
    prefix := make([]int64, n)
    suffix := make([]int64, n)
    prefix[0] = int64(nums[0])
    for i := 1; i < n; i++ {
        prefix[i] = prefix[i-1] + int64(nums[i])
    }
    suffix[n-1] = int64(nums[n-1])
    for i := n-2; i >= 0; i-- {
        suffix[i] = suffix[i+1] + int64(nums[i])
    }
    ans := prefix[0]
    for i := 0; i < n; i++ {
        if prefix[i] > ans { ans = prefix[i] }
        if suffix[i] > ans { ans = suffix[i] }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public long maximumSumScore(int[] nums) {
        int n = nums.length;
        long[] prefix = new long[n], suffix = new long[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; ++i) prefix[i] = prefix[i-1] + nums[i];
        suffix[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; --i) suffix[i] = suffix[i+1] + nums[i];
        long ans = Long.MIN_VALUE;
        for (int i = 0; i < n; ++i)
            ans = Math.max(ans, Math.max(prefix[i], suffix[i]));
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maximumSumScore(nums: IntArray): Long {
        val n = nums.size
        val prefix = LongArray(n)
        val suffix = LongArray(n)
        prefix[0] = nums[0].toLong()
        for (i in 1 until n) prefix[i] = prefix[i-1] + nums[i]
        suffix[n-1] = nums[n-1].toLong()
        for (i in n-2 downTo 0) suffix[i] = suffix[i+1] + nums[i]
        var ans = Long.MIN_VALUE
        for (i in 0 until n)
            ans = maxOf(ans, maxOf(prefix[i], suffix[i]))
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maximumSumScore(self, nums: list[int]) -> int:
        n = len(nums)
        prefix = [0] * n
        suffix = [0] * n
        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = prefix[i-1] + nums[i]
        suffix[-1] = nums[-1]
        for i in range(n-2, -1, -1):
            suffix[i] = suffix[i+1] + nums[i]
        ans = float('-inf')
        for i in range(n):
            ans = max(ans, prefix[i], suffix[i])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn maximum_sum_score(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut prefix = vec![0i64; n];
        let mut suffix = vec![0i64; n];
        prefix[0] = nums[0] as i64;
        for i in 1..n { prefix[i] = prefix[i-1] + nums[i] as i64; }
        suffix[n-1] = nums[n-1] as i64;
        for i in (0..n-1).rev() { suffix[i] = suffix[i+1] + nums[i] as i64; }
        let mut ans = i64::MIN;
        for i in 0..n {
            ans = ans.max(prefix[i]).max(suffix[i]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maximumSumScore(nums: number[]): number {
        const n = nums.length;
        const prefix: number[] = Array(n).fill(0);
        const suffix: number[] = Array(n).fill(0);
        prefix[0] = nums[0];
        for (let i = 1; i < n; ++i) prefix[i] = prefix[i-1] + nums[i];
        suffix[n-1] = nums[n-1];
        for (let i = n-2; i >= 0; --i) suffix[i] = suffix[i+1] + nums[i];
        let ans = -Infinity;
        for (let i = 0; i < n; ++i)
            ans = Math.max(ans, prefix[i], suffix[i]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We scan the array twice for prefix and suffix sums.
  • 🧺 Space complexity: O(n), for the prefix and suffix arrays.