3727. Maximum Alternating Sum of Squares

3727. Maximum Alternating Sum of Squares

Difficulty: Medium

Topics: Senior, Array, Greedy, Sorting, Weekly Contest 473

You are given an integer array nums. You may rearrange the elements in any order.

The alternating score of an array arr is defined as:

• score = arr[0]² - arr[1]² + arr[2]² - arr[3]² + ...

Return an integer denoting the maximum possible alternating score of nums after rearranging its elements.

Example 1:

• Input: nums = [1,2,3]
• Output: 12
• Explanation:
  • A possible rearrangement for nums is [2,1,3], which gives the maximum alternating score among all possible rearrangements.
  • The alternating score is calculated as: score = 2² - 1² + 3² = 4 - 1 + 9 = 12

Example 2:

• Input: nums = [1,-1,2,-2,3,-3]
• Output: 16
• Explanation:
  • A possible rearrangement for nums is [-3,-1,-2,1,3,2], which gives the maximum alternating score among all possible rearrangements.
  • The alternating score is calculated as: score = (-3)² - (-1)² + (-2)² - (1)² + (3)² - (2)² = 9 - 1 + 4 - 1 + 9 - 4 = 16

Example 3:

• Input: nums = [5]
• Output: 25

Example 4:

• Input: nums = [1,2]
• Output: 3

Example 5:

• Input: nums = [-5,5]
• Output: 0

Example 6:

• Input: nums = [0,0,0]
• Output: 0

Example 7:

• Input: nums = [1,2,3,4]
• Output: 20

Example 8:

• Input: nums = [-4,-3,-2,-1,0]
• Output: 28

Example 9:

• Input: nums = [100,-100,1]
• Output: 19999

Constraints:

• 1 <= nums.length <= 10⁵
• -4 * 10⁴ <= nums[i] <= 4 * 10⁴

Hint:

1. The score uses squares of values. The original signs of nums don't affect the squared terms.
2. In the alternating sum, even indices contribute positively and odd indices negatively.

Solution:

We maximize the alternating score by ignoring the original signs of nums, since only squares matter. After squaring all values and sorting them descending, we place the largest ceil(n/2) squares into positive positions and the remaining smaller squares into negative positions.

Approach

• Convert every nums[i] into nums[i] * nums[i].
• Sort these squared values in descending order.
• There are positiveCount = ceil(n / 2) positive slots.
• Add the first positiveCount largest squares to the score.
• Subtract all remaining smaller squares from the score.
• Return the resulting score.

Let's implement this solution in PHP: 3727. Maximum Alternating Sum of Squares

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function maxAlternatingSum(array $nums): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxAlternatingSum([1,2,3]) .  "\n";                // Output: 12
echo maxAlternatingSum([1,-1,2,-2,3,-3]) .  "\n";       // Output: 16
echo maxAlternatingSum([5]) .  "\n";                    // Output: 25
echo maxAlternatingSum([1,2]) .  "\n";                  // Output: 3
echo maxAlternatingSum([-5,5]) .  "\n";                 // Output: 0
echo maxAlternatingSum([0,0,0]) .  "\n";                // Output: 0
echo maxAlternatingSum([1,2,3,4]) .  "\n";              // Output: 20
echo maxAlternatingSum([-4,-3,-2,-1,0]) .  "\n";        // Output: 28
echo maxAlternatingSum([100,-100,1]) .  "\n";           // Output: 19999
?>

Explanation:

• The alternating score is:
  • arr[0]² - arr[1]² + arr[2]² - arr[3]² + ...
• Even indices contribute positively, odd indices contribute negatively.
• For length n:
  • Positive slots = ceil(n / 2)
  • Negative slots = floor(n / 2)
• To maximize the result, we want the largest possible squares in positive slots and the smallest possible squares in negative slots.
• If a larger square were in a negative slot and a smaller square in a positive slot, swapping them would increase the score.
• Therefore, sorting descending and assigning the first ceil(n/2) values to positive positions is optimal.

Complexity Analysis

• Time Complexity: O(n log n) due to sorting.
• Space Complexity: O(n) for the squared-values array.
• n <= 10⁵, so this is efficient.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub