Maximum Calories Burnt from Jumps - Solution & Explanation

Problem Overview: You are given an array representing the heights (or intensity) of jumps. The calories burned between consecutive jumps depend on the difference between their heights. The goal is to arrange the jumps in an order that maximizes the total calories burned.

Approach 1: Brute Force Permutations (O(n!))

The most direct idea is to generate every possible ordering of the jumps and compute the total calories burned for each arrangement. For each permutation, iterate through the array and sum the absolute differences between consecutive elements. Track the maximum value across all permutations. This guarantees the optimal answer but quickly becomes impractical since the number of permutations grows factorially. Time complexity is O(n!) and space complexity is O(n) for recursion and permutation storage.

Approach 2: Greedy + Sorting with Two Pointers (O(n log n))

A key observation: large differences between consecutive jumps produce more calories. To maximize the total, you want large and small values to appear next to each other as often as possible. Start by sorting the array. Then construct the sequence by alternately taking the smallest and largest remaining elements using a two-pointer strategy. This arrangement spreads extremes apart and increases the sum of absolute differences.

Use two pointers: one at the beginning and one at the end of the sorted array. Pick elements from opposite ends and place them into the result sequence in alternating order. Finally, compute the total calories burned by iterating through the constructed sequence and summing |a[i] - a[i-1]|. Sorting costs O(n log n), while building the sequence and computing the sum takes O(n). Space complexity is O(n) for the arranged sequence.

This greedy idea works because maximizing local differences between neighbors contributes directly to the global objective. The technique frequently appears in problems involving maximizing pairwise gaps or arranging numbers for maximum contrast.

Related concepts include array manipulation, sorting, and the two pointers technique, which help efficiently build the optimal arrangement.

Recommended for interviews: The Greedy + Sorting solution. Interviewers expect you to recognize that maximizing adjacent differences requires pairing extremes. Mentioning the brute force permutation approach first shows you understand the search space, but identifying the greedy ordering demonstrates strong algorithmic intuition.