LeetCode 2219. Maximum Sum Score of Array Solution in Java, C++, Python & More | Explanation + Code

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

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 = ∑_{i=0}^n-1 nums[i].

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

After the traversal, return the answer ans.

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

PythonJavaC++GoTypeScriptRustJavaScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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) }(code-box)

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; }(code-box)

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 } }(code-box)

/** * @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; };(code-box)