2219. Maximum Sum Score of Array

Problem Description

In this problem, you're provided with an array of integers named nums indexed from 0 to n-1, where n is the length of the array. You need to calculate what is called the sum score for each index of the array. The sum score at a particular index i is defined as the maximum between two sums:

The sum of elements from the start of the array up through index i.
The sum of elements from index i through the end of the array.

Your task is to determine the maximum sum score that can be obtained at any index i in the provided array.

Intuition

The key to solving this problem lies in understanding prefix and suffix sums, which are cumulative sums of the elements of the array from the beginning up to a certain element, and from a certain element to the end, respectively.

Calculate the prefix sum for the array, which gives you the sum of elements from the start of the array up to each index i. This is stored in an array s where s[i] would represent the sum of elements from nums[0] to nums[i-1].
Iterate through the array to calculate the sum score at each index. This can be done in a single pass after the prefix sum array has been built:
- For each index i, determine the sum from the start of the array to index i. This is given by the prefix sum at index i + 1 (since we initialized prefix sum with 0 at the beginning).
- To determine the sum from index i to the end of the array, subtract the prefix sum up to index i from the total sum of the array, which is the last element of the prefix sum array.
- The sum score at index i is the maximum of these two sums.
After calculating the sum scores for each index, the maximum sum score is the answer, which represents the maximum value obtained from any index i.

By using a prefix sum array and iterating through the array only once, we can solve this problem efficiently with a time complexity of O(n), where n is the length of the input array.

Learn more about Prefix Sum patterns.

Solution Approach

The given solution implements the intuition behind the problem in Python. It utilizes the accumulate function from the itertools module to generate prefix sums efficiently and a simple loop to compare sums at each index.

Here is a step-by-step explanation of the provided code:

Step 1: Calculate Prefix Sums

The line s = [0] + list(accumulate(nums)) is crucial. It creates a new list s that stores the prefix sums of the nums array. The accumulate function takes each element and adds it to the sum of all the previous elements. The [0] at the start of this list is to simplify calculations for the prefix sum at index 0. After this line, s[i] will contain the sum of nums from nums[0] up to nums[i-1].

Step 2: Iterate to Find Maximum Sum Score

The expression (max(s[i + 1], s[-1] - s[i]) for i in range(len(nums))) uses a generator to calculate sum scores without storing them. For each index i in nums, it calculates two sums:

s[i + 1] gives us the sum of elements from the beginning of the array to index i (prefix sum).
s[-1] - s[i] gives us the sum of elements from index i to the end of the array (this works because s[-1] represents the total sum of the array, which is the last element in the prefix sums list).

Step 3: Find the Maximum Value

The max function is used again to find the maximum sum score from the generator. This is the maximum value that can be obtained from any of the sum scores calculated in the previous step.

The result of the max function call is returned as the final answer, representing the overall maximum sum score at any index i in the input nums array.

Algorithm Pattern

The algorithm follows a pattern often used for solving cumulative sum problems: it first preprocesses the input array to build a data structure (in this case, a prefix sum array), enabling efficient calculations of subarray sums. It then iterates through the array a single time to find the desired maximum value.

Data Structure

An array (or list in Python) is the primary data structure used here for storing the prefix sums.

Time Complexity

Since each of the steps above runs in O(n) time, where n is the length of the nums array, and there are no nested loops, the overall time complexity of the function is O(n).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Consider the array nums = [3, 1, -2, 5, 2]. Our goal is to find the maximum sum score at any index i after performing the calculations as outlined in the problem description.

Step 1: Calculate Prefix Sums

First, we calculate the prefix sums for the array nums.

Initialize an array s with an extra 0 at the beginning to simplify the prefix sum calculations.
Using the accumulate function from the itertools module, we generate the prefix sums of nums. This results in the following array:
```
s = [0] + list(accumulate([3, 1, -2, 5, 2])) = [0, 3, 4, 2, 7, 9]
```
In this array, s[i] represents the sum of elements from nums[0] to nums[i-1]. For example, s[3] = 2 corresponds to the sum of elements 3 + 1 - 2.

Step 2: Iterate to Find Maximum Sum Score

Next, we iterate through the array to calculate the sum score at each index i.

For index i = 0, the sum from the start to index 0 is s[1] = 3, and from index 0 to the end is s[-1] - s[0] = 9 - 0 = 9. The sum score for index 0 is the maximum of these two, which is 9.
For index i = 1, the sum from the start to index 1 is s[2] = 4, and from index 1 to the end is s[-1] - s[1] = 9 - 3 = 6. The sum score for index 1 is the maximum, which is 6.

Continuing in this way for each index, we compute the sum score:

Index 0: max(3, 9) = 9
Index 1: max(4, 6) = 6
Index 2: max(4, 7) = 7
Index 3: max(2, 7) = 7
Index 4: max(7, 2) = 7

Step 3: Find the Maximum Value

Finally, we find the maximum sum score from all the calculated sum scores, which is 9 (obtained at index 0).

Using this approach, we can efficiently determine that the maximum sum score for the array [3, 1, -2, 5, 2] is 9. The solution only iterates through the array once (after computing the prefix sums), thus ensuring a time complexity of O(n).

Solution Implementation

1from typing import List
2from itertools import accumulate
3
4class Solution:
5    def maximum_sum_score(self, nums: List[int]) -> int:
6        # Prefix sum array initialization with an extra zero at the beginning
7        # to handle the case where we accumulate from the start of the array.
8        prefix_sums = [0] + list(accumulate(nums))
9
10        # Calculate the maximum sum score by iterating through each element
11        # in the nums array while taking into account both the sum of elements 
12        # before the current element (prefix sum) and the sum of elements 
13        # after the current element (suffix sum).
14        max_score = max(
15            max(prefix_sums[i + 1], prefix_sums[-1] - prefix_sums[i]) 
16            for i in range(len(nums))
17        )
18
19        # Return the maximum sum score found.
20        return max_score
21

1class Solution {
2    public long maximumSumScore(int[] nums) {
3        int length = nums.length;
4        // Create an array to store the prefix sums
5        long[] prefixSums = new long[length + 1];
6
7        // Calculate the prefix sums
8        for (int i = 0; i < length; ++i) {
9            prefixSums[i + 1] = prefixSums[i] + nums[i];
10        }
11
12        // Initialize the maximum sum as the smallest possible value
13        long maxSum = Long.MIN_VALUE;
14
15        // Find the maximum sum score by choosing the larger between
16        // the sum from the start to the current element or
17        // the sum from the current element to the end
18        for (int i = 0; i < length; ++i) {
19            long sumFromStart = prefixSums[i + 1];
20            long sumFromEnd = prefixSums[length] - prefixSums[i];
21            maxSum = Math.max(maxSum, Math.max(sumFromStart, sumFromEnd));
22        }
23
24        // Return the maximum score found
25        return maxSum;
26    }
27}
28

1#include <vector>
2#include <algorithm> // for std::max
3#include <climits> // For INT_MIN constant
4
5class Solution {
6public:
7    long long maximumSumScore(vector<int>& nums) {
8        int n = nums.size(); // Get the size of the input vector
9        vector<long long> prefixSums(n + 1, 0); // Initialize prefix sums vector with an extra element
10      
11        // Calculate prefix sums for the entire array
12        for (int i = 0; i < n; ++i) {
13            prefixSums[i + 1] = prefixSums[i] + nums[i];
14        }
15      
16        long long maxScore = LLONG_MIN; // Initialize the maxScore with the smallest possible value for long long
17      
18        // Iterate through the array to find the maximum sum score
19        for (int i = 0; i < n; ++i) {
20            // For each element, we consider two cases:
21            // 1. The sum of elements from start up to i (prefixSums[i + 1])
22            // 2. The sum of elements from i to the end of the array (prefixSums[n] - prefixSums[i])
23            // The maximum of these two values is compared with the maxScore to update it
24            maxScore = max(maxScore, max(prefixSums[i + 1], prefixSums[n] - prefixSums[i]));
25        }
26      
27        // Return the maximum sum score
28        return maxScore;
29    }
30};
31

1function maximumSumScore(nums: number[]): number {
2    const numElements = nums.length; // Total number of elements in the array
3
4    // Create and initialize a prefix sum array with an additional
5    // first element set to 0 for ease of calculation
6    let prefixSums = new Array(numElements + 1).fill(0);
7  
8    // Populate the prefix sum array with cumulative sums,
9    // where prefixSums[i] will hold the sum of nums[0] to nums[i - 1]
10    for (let i = 0; i < numElements; ++i) {
11        prefixSums[i + 1] = prefixSums[i] + nums[i];
12    }
13
14    // Initialize the answer variable to the minimum possible value
15    // since we are looking for the maximum
16    let maxSumScore = -Infinity;
17
18    // Iterate through each element and calculate the sum score
19    // by taking the higher value between:
20    // 1. The sum of elements from the start to the current index (inclusive)
21    // 2. The sum of elements from the current index (excluding) to the end
22    for (let i = 0; i < numElements; ++i) {
23        // Compare the sum score at each index with the maxSumScore found so far
24        maxSumScore = Math.max(
25            maxSumScore, 
26            Math.max(prefixSums[i + 1], prefixSums[numElements] - prefixSums[i])
27        );
28    }
29
30    // Return the maximum sum score found
31    return maxSumScore;
32}
33

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of elements in the input list nums. This is due to the following reasons:

We first precompute the prefix sums with accumulate(nums), which takes O(n) time.
Then, we perform a single pass over the nums list to calculate the maximum sum score. During each iteration, we calculate the maximum between s[i + 1] and s[-1] - s[i]. There are n such calculations, each taking constant time.

The space complexity of the code is O(n). This is because we are creating a new list called s that contains the prefix sums of the nums array, which is of size n + 1.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know

2219. Maximum Sum Score of Array

Problem Description

Intuition

Solution Approach

Step 1: Calculate Prefix Sums

Step 2: Iterate to Find Maximum Sum Score

Step 3: Find the Maximum Value

Algorithm Pattern

Data Structure

Time Complexity

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Example Walkthrough

Step 1: Calculate Prefix Sums

Step 2: Iterate to Find Maximum Sum Score

Step 3: Find the Maximum Value

Solution Implementation

Time and Space Complexity

Recommended Readings