Skip to content

3730. Maximum Calories Burnt from Jumps πŸ”’

Description

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.

 

Example 1:

Input: heights = [1,7,9]

Output: 181

Explanation:​​​​​​​

The optimal sequence is [9, 1, 7].

  • Initial jump from the ground to heights[2] = 9: (0 - 9)2 = 81.
  • Next jump to heights[0] = 1: (9 - 1)2 = 64.
  • Final jump to heights[1] = 7: (1 - 7)2 = 36.

Total calories burned = 81 + 64 + 36 = 181.

Example 2:

Input: heights = [5,2,4]

Output: 38

Explanation:

The optimal sequence is [5, 2, 4].

  • Initial jump from the ground to heights[0] = 5: (0 - 5)2 = 25.
  • Next jump to heights[1] = 2: (5 - 2)2 = 9.
  • Final jump to heights[2] = 4: (2 - 4)2 = 4.

Total calories burned = 25 + 9 + 4 = 38.

Example 3:

Input: heights = [3,3]

Output: 9

Explanation:

The optimal sequence is [3, 3].

  • Initial jump from the ground to heights[0] = 3: (0 - 3)2 = 9.
  • Next jump to heights[1] = 3: (3 - 3)2 = 0.

Total calories burned = 9 + 0 = 9.

 

Constraints:

  • 1 <= n == heights.length <= 105
  • 1 <= heights[i] <= 105

Solutions

Solution 1: Greedy + Sorting

According to the problem statement, the order of jumps affects the total calories burned. To maximize calorie consumption, we can use a greedy strategy by prioritizing jumps with the largest height differences.

Therefore, we can first sort the block heights, then start jumping from the highest block, then to the lowest block, and so on, until all blocks have been jumped on.

The specific steps are as follows:

  1. Sort the array \(\text{heights}\).
  2. Initialize the variable \(\text{pre} = 0\) to represent the height of the previous block, and \(\text{ans} = 0\) to represent the total calories burned.
  3. Use two pointers: the left pointer \(\text{l}\) points to the beginning of the array, and the right pointer \(\text{r}\) points to the end of the array.
  4. While \(\text{l} < \text{r}\), do the following:
    1. Calculate the calories burned from the previous block to the block pointed to by the right pointer and add it to \(\text{ans}\).
    2. Calculate the calories burned from the block pointed to by the right pointer to the block pointed to by the left pointer and add it to \(\text{ans}\).
    3. Update \(\text{pre}\) to the height of the block pointed to by the left pointer.
    4. Move the left pointer one step to the right and the right pointer one step to the left.
  5. Finally, calculate the calories burned from the previous block to the middle block and add it to \(\text{ans}\).

The time complexity is \(O(n \log n)\) and the space complexity is \(O(\log n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxCaloriesBurnt(self, heights: list[int]) -> int:
        heights.sort()
        pre = 0
        l, r = 0, len(heights) - 1
        ans = 0
        while l < r:
            ans += (heights[r] - pre) ** 2
            ans += (heights[l] - heights[r]) ** 2
            pre = heights[l]
            l, r = l + 1, r - 1
        ans += (heights[r] - pre) ** 2
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public long maxCaloriesBurnt(int[] heights) {
        Arrays.sort(heights);
        long ans = 0;
        int pre = 0;
        int r = heights.length - 1;
        for (int l = 0; l < r; ++l, --r) {
            ans += 1L * (heights[r] - pre) * (heights[r] - pre);
            ans += 1L * (heights[l] - heights[r]) * (heights[l] - heights[r]);
            pre = heights[l];
        }
        ans += 1L * (heights[r] - pre) * (heights[r] - pre);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    long long maxCaloriesBurnt(vector<int>& heights) {
        ranges::sort(heights);
        long long ans = 0;
        int pre = 0;
        int r = heights.size() - 1;
        for (int l = 0; l < r; ++l, --r) {
            ans += 1LL * (heights[r] - pre) * (heights[r] - pre);
            ans += 1LL * (heights[l] - heights[r]) * (heights[l] - heights[r]);
            pre = heights[l];
        }
        ans += 1LL * (heights[r] - pre) * (heights[r] - pre);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maxCaloriesBurnt(heights []int) (ans int64) {
    sort.Ints(heights)
    pre := 0
    l, r := 0, len(heights)-1
    for l < r {
        ans += int64(heights[r]-pre) * int64(heights[r]-pre)
        ans += int64(heights[l]-heights[r]) * int64(heights[l]-heights[r])
        pre = heights[l]
        l++
        r--
    }
    ans += int64(heights[r]-pre) * int64(heights[r]-pre)
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function maxCaloriesBurnt(heights: number[]): number {
    heights.sort((a, b) => a - b);
    let ans = 0;
    let pre = 0;
    let [l, r] = [0, heights.length - 1];
    while (l < r) {
        ans += (heights[r] - pre) ** 2;
        ans += (heights[l] - heights[r]) ** 2;
        pre = heights[l];
        l++;
        r--;
    }
    ans += (heights[r] - pre) ** 2;
    return ans;
}

Comments