Maximum Sum Score of Array Solution in C++

class Solution {
 public:
  long long maximumSumScore(vector& nums) {
    long ans = LONG_MIN;
    long prefix = 0;
    long sum = accumulate(nums.begin(), nums.end(), 0L);

    for (const int num : nums) {
      prefix += num;
      ans = max({ans, prefix, sum - prefix + num});
    }

    return ans;
  }
};
    

Problem Description

The “Maximum Sum Score of Array” problem is akin to finding the best way to split a pizza among friends without causing any disputes. The goal is to maximize happiness (or in this case, the sum score) while ensuring fairness.

Given an array of integers, your task is to find the maximum sum score achievable by cleverly partitioning the array. Think of it as balancing your time between binge-watching your favorite series and being productive—spoiler alert: binge-watching usually wins!

Approach

The approach is straightforward. We maintain a running prefix sum while iterating through the array. For each element, we calculate the maximum score by considering three scenarios: the current prefix sum, the maximum score from previous elements, and the score obtained by subtracting the current prefix from the total sum. It’s like strategizing the best moves in a game!

Time and Space Complexity

Time Complexity

O(n), where n is the number of elements in the array. We traverse the array once.

Space Complexity

O(1), as we use a constant amount of space for our variables.

Real-World Example

Imagine you’re at a buffet with a limited plate size. You want to maximize the delicious food you can fit without spilling over. Each dish represents an element in the array, and your goal is to find the best combination of dishes that gives you maximum satisfaction (or sum score). Just like in the problem, strategic choices are essential to leave the buffet feeling like a champion!