2024-12-21：从魔法师身上吸取的最大能量。用go语言，在一个神秘的地牢里，有 n 名魔法师排成一列。每位魔法师都有一个能量属性，有的提供正能量，而有的则会消耗你的能量。

你被施加了一种诅咒，吸收来自第 i 位魔法师的能量后，你会立即被传送到第 (i + k) 位魔法师。在这个过程中，你会不断进行这种跳跃，直到到达一个不存在的魔法师为止。

换句话说，你可以选择一个起始魔法师，并且以 k 为步长进行跳跃，直到超出魔法师的范围。在这个过程中，你需要计算出可以获得的最大能量。

给定一个能量数组和一个整数 k，返回你能够获得的最高能量值。

1 <= energy.length <= 100000。

-1000 <= energy[i] <= 1000。

1 <= k <= energy.length - 1。

输入： energy = [5,2,-10,-5,1], k = 3。

输出： 3。

解释：可以从魔法师 1 开始，吸收能量 2 + 1 = 3。

答案2024-12-21：

chatgpt[1]

题目来自leetcode3147。

大体步骤如下：

1.初始化n为energy数组的长度，ans为math.MinInt（即int类型的最小值）。

2.从n-k的位置开始向后遍历数组energy。

3.对于当前位置i，初始化s为0，从i开始向前以步长k遍历每个魔法师。

4.在每个位置上，累加能量值到s中，并更新ans为当前的ans和s中的较大值。

5.返回最终的ans作为结果。

总的时间复杂度：

• 外层循环迭代次数为k，内层从i位置开始以步长k遍历，需要O(n/k)次操作。• 所以总的时间复杂度为O(k * n/k) = O(n)。

总的额外空间复杂度：

• 除了保存输入参数和几个变量外，算法并没有使用额外的空间存储数据。• 因此总的额外空间复杂度是O(1)（常数空间复杂度）。Go完整代码如下：package mainimport ( "fmt" "math")func maximumEnergy(energy []int, k int) int { n := len(energy) ans := math.MinInt for i := n - k; i < n; i++ { s := 0 for j := i; j >= 0; j -= k { s += energy[j] ans = max(ans, s) } } return ans}func main() { energy := []int{5, 2, -10, -5, 1} k := 3 fmt.Println(maximumEnergy(energy, k))}

Rust完整代码如下：use std::cmp;fn maximum_energy(energy: Vec<i32>, k: usize) -> i32 { let n = energy.len(); let mut ans = i32::MIN; for i in (n - k..n).rev() { let mut s = 0; let mut j = i as isize; while j >= 0 { s += energy[j as usize]; ans = cmp::max(ans, s); j -= k as isize; } } ans}fn main() { let energy = vec![5, 2, -10, -5, 1]; let k = 3; println!("{}", maximum_energy(energy, k));}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP