Maximum calories burnt from jumps

Array Two Pointers Greedy Sorting

72.5% acceptance

Mar 31, 2026

You are given an integer array heights of size n, where heights[i] represents the height of the ith block in an exercise routine. You start on the ground (height 0) and must jump onto each block exactly once in any order. The calories burned for a jump from a block of height a to a block of height b is (a - b)2. The calories burned for the first jump from the ground to the chosen first block heights[i] is (0 - heights[i])2. Return the maximum total calories you can burn by selecting an optimal jumping sequence. Note: Once you jump onto the first block, you cannot return to the ground.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_calories_burnt(heights: Vec<i32>) -> i64 {
    let mut h = heights;
    h.sort();
    let n = h.len();
    let mut order = Vec::with_capacity(n);
    let (mut lo, mut hi) = (0, n - 1);
    let mut take_hi = true;
    while lo <= hi {
      if take_hi {
        order.push(h[hi] as i64);
        if hi == 0 { break; }
        hi -= 1;
      } else {
        order.push(h[lo] as i64);
        lo += 1;
      }
      take_hi = !take_hi;
    }
    let mut total = order[0] * order[0];
    for i in 1..order.len() {
      let d = order[i - 1] - order[i];
      total += d * d;
    }
    total
  }
}