FastPrep

Description

Solutions

Find Maximum Calories

👩‍🎓 NEW GRAD📚RELATED PROBLEMS

A user is using the Amazon fitness tracker, and they are engaged in a jumping exercise routine. The user is positioned on the ground, and there are n stones, each placed at different heights. The height of the ith stone is represented by height[i] meters.

The goal is to maximize the calorie burn during this exercise, and the calories burned when jumping from the ith stone to the jth stone is calculated as (height[i] - height[j])^2.

The user intends to practice jumping on each stone exactly once but can choose the order in which they jump. Since the user is looking to optimize their calorie burn for this single session, the task is to determine the maximum amount of calories that can be burned during the exercise.

Formally, given an array height of size n, representing the height of each stone, find the maximum amount of calories the user can burn.

Note that the user can jump from any stone to any stone, and the ground's height is 0 and once user jumps to stone from ground, he/she can never go back to ground.

Function Description

Complete the function findMaximumCalories in the editor below.

findMaximumCalories has the following parameters:

int height[n]: the height of each stone

Returns

long: the maximum amount of calories the user can burn.

Example 1:

Input:  height = [5, 2, 5]
Output: 43 
Explanation:
      
      The user will jump in the following way:
      Ground → 3rd stone → 2nd stone → 1st stone
      

      
      The calories she will burn can be calculated as:
      = (0-height[2])^2 + (height[2]-height[1])^2 + (height[1]-height[0])^2
      = 25 + 9 + 9
      = 43
      

      
      It can be shown it is not possible to burn more than 43 units of calories, hence, the answer is 43.

Constraints:

1 ≤ n ≤ 10^5
1 ≤ height[i] ≤ 46340