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

题目来自 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));}