algorithms/leetcode/3730-MaximumCaloriesBurntFromJumps.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package main

// 3730. Maximum Calories Burnt from Jumps
// 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.
//     1. The calories burned for a jump from a block of height a to a block of height b is (a - b)^2.
//     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 <= 10^5
//     1 <= heights[i] <= 10^5

import "fmt"
import "sort"
import "math"

func maxCaloriesBurnt(heights []int) int64 {
    sort.Ints(heights)
    res, pre, left, right, flag := 0, 0, 0, len(heights) - 1, true
    for {
        if flag {
            res += int(math.Pow(float64(heights[right] - pre), 2))
            pre = heights[right]
            right--
            flag = false
        } else {
            res += int(math.Pow(float64(heights[left] - pre), 2))
            pre = heights[left]
            left++
            flag = true
        }
        if left > right {
            break
        }
    }
    return int64(res)
}

func maxCaloriesBurnt1(heights []int) int64 {
    sort.Ints(heights)
    n := len(heights)
    i, j := 0, n - 1
    res := int64(heights[j] * heights[j])
    for i < j {
        val := heights[j] - heights[i]
        res += int64(val * val)
        j--
        if j > i {
            val := heights[j] - heights[i]
            res += int64(val * val)
        }
        i++
    }
    return res
}

func main() {
    // 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.
    fmt.Println(maxCaloriesBurnt([]int{1,7,9})) // 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.
    fmt.Println(maxCaloriesBurnt([]int{5,2,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.
    fmt.Println(maxCaloriesBurnt([]int{3,3})) // 9

    fmt.Println(maxCaloriesBurnt([]int{1,2,3,4,5,6,7,8,9})) // 285
    fmt.Println(maxCaloriesBurnt([]int{9,8,7,6,5,4,3,2,1})) // 285

    fmt.Println(maxCaloriesBurnt1([]int{1,7,9})) // 181
    fmt.Println(maxCaloriesBurnt1([]int{5,2,4})) // 38
    fmt.Println(maxCaloriesBurnt1([]int{3,3})) // 9
    fmt.Println(maxCaloriesBurnt1([]int{1,2,3,4,5,6,7,8,9})) // 285
    fmt.Println(maxCaloriesBurnt1([]int{9,8,7,6,5,4,3,2,1})) // 285
}