Maximum alternating sum of squares

Array Greedy Sorting

61.1% acceptance

Feb 24, 2026

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]^2 - arr[1]^2 + arr[2]^2 - arr[3]^2 + ... Return an integer denoting the maximum possible alternating score of nums after rearranging its elements.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
    // Sort by absolute value ascending
    let mut vals: Vec<i64> = nums.iter().map(|&x| (x as i64).abs()).collect();
    vals.sort_unstable();
    let n = vals.len();
    let odd_count = n / 2; // positions 1, 3, 5, ... (subtract)
    // Assign smallest to odd positions (minimize subtraction), rest to even (maximize addition)
    let mut score = 0i64;
    for i in 0..odd_count {
      score -= vals[i] * vals[i]; // smallest go to subtract positions
    }
    for i in odd_count..n {
      score += vals[i] * vals[i]; // largest go to add positions
    }
    score
  }
}