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：
题目来自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 main
import (
"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));
}
