3147. Taking Maximum Energy From the Mystic Dungeon

Leetcode link

题目简介

本题提供两个参数：

• energy：数组，代表你经过每一个元素将会得到的能量，能量有可能为负的
• k：数字，代表你每次经过元素需要略过的元素数量，假设有一个数组 [1, 2, 3, 4, 5]，而 k = 3，则如果你从第一个元素开始的话，你遍历的数组会是 [1, 4]

题目要求我们可以从数组的任何位置开始遍历，让我们求能够获得的最大能量是多少

解题思路1

从题目描述中我们不难看出，对于数组的最后 k 项，能够获得的能量就是 energy 数组的最后 k 个元素本身

所以我们接下来的关键在于，要怎么找到元素 i 与元素 i+k 之间的关系

假设我们使用数组 dp 来保存从当前元素开始遍历所能获得的能量总和，那么我们不难得出：

dp[i] = dp[i+k] + energy[i]

解释：假设 i+k 是 energy 的最后一个元素，则我们从其 k 个元素前开始获取能量，我们可以多获得 energy[i] 个能量

有了这个等式，我们只要从后往前遍历数组，就能够得到所有的 dp 数组元素了，最后只要取最大值返回就是我们的答案了

Javascript

/**
 * @param {number[]} energy
 * @param {number} k
 * @return {number}
 */
var maximumEnergy = function (energy, k) {
    const dp = [...energy]

    for (let i = dp.length - 1 - k; i >= 0; i--) {
        dp[i] = dp[i+k] + energy[i]
    }
    return Math.max(...dp)
};

解题思路2

如果仔细看我们的上一个解题思路，我们不难发现数组 dp 其实是可以被优化掉的

我们还是那个关键的等式：dp[i] = dp[i+k] + energy[i]

但是这次我们将一次的数组遍历拆开，拆成 k 次遍历，每次从 dp.length - k - i (0<=i<k) 开始遍历

并且记录遍历过程中的最大值，记录下来，等遍历结束直接返回就好

Javascript

/**
 * @param {number[]} energy
 * @param {number} k
 * @return {number}
 */
var maximumEnergy = function (energy, k) {
    let res = Number.MIN_SAFE_INTEGER
    let step = k

    while (step > 0) {
        let totalEnergy = 0
        for (let i = energy.length - step; i >= 0; i -= k) {
            totalEnergy += energy[i]
            res = Math.max(totalEnergy, res)
        }
        step--
    }
    return res
};