2025-04-14：到达数组末尾的最大得分。用go语言，给定一个长度为 n 的整数数组 nums，你需要从下标 0 开始，最终

2025-04-14：到达数组末尾的最大得分。用go语言，给定一个长度为 n 的整数数组 nums，你需要从下标 0 开始，最终到达下标 n - 1。你可以每次只向右移动到一个更大的下标。

当你从下标 i 跳到下标 j 时，你获得的得分为 (j - i) * nums[i]。最终，你需要计算出能够获得的最大总得分，并返回该值。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

输入：nums = [1,3,1,5]。

输出：7。

解释：

一开始跳到下标 1 处，然后跳到最后一个下标处。总得分为 1 * 1 + 2 * 3 = 7 。

题目来自leetcode3282。

解决步骤：

1. 1. 关键观察： 总得分可以分解为每一步跳跃的得分之和。假设在某个位置i，存在更大的元素j，则最优策略是尽可能跳到该元素的位置。然而，通过观察发现，总得分等于数组前n-1个元素的前缀最大值之和。
2. 2. 前缀最大值之和的直觉： 每次跳跃的得分可以视为当前最大值在后续位置上的持续贡献。例如，从i跳到j，在i到j-1之间的所有位置，当前最大值保持为nums[i]。遍历时维护当前最大值，并将每一步的当前最大值累加，最终总和即为最大得分。
3. 3. 具体实现：
   • • 初始化当前最大值mx为0，总得分ans为0。
   • • 遍历数组的前n-1个元素（因为最后一个元素无法跳跃）：
     • • 更新当前最大值mx为当前元素与mx的较大值。
     • • 将mx累加到总得分ans中。
   • • 遍历完成后，ans即为最大总得分。

时间复杂度：

• • O(n)，其中n为数组长度。只需一次遍历即可完成所有计算。

额外空间复杂度：

• • O(1)，仅使用固定数量的变量（mx和ans），不随输入规模变化。

示例验证： 以输入nums = [1,3,1,5]为例：

• • 遍历前三个元素：
  • • 第1个元素1，mx更新为1，得分累加1。
  • • 第2个元素3，mx更新为3，得分累加3。
  • • 第3个元素1，mx保持3，得分累加3。
• • 总得分1 + 3 + 3 = 7，与预期结果一致。

总结： 通过维护当前最大值并累加前缀最大值之和，该算法高效地解决了问题，时间和空间复杂度均为最优。

Go完整代码如下：

package main

import (
    "fmt"
)

func findMaximumScore(nums []int) (ans int64) {
    mx := 0
    for _, x := range nums[:len(nums)-1] {
        mx = max(mx, x)
        ans += int64(mx)
    }
    return
}

func main() {
    nums := []int{1, 3, 1, 5}
    results := findMaximumScore(nums)
    fmt.Println(results)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def find_maximum_score(nums):
    ans = 0
    mx = 0
    # 遍历数组的前 n-1 个元素
    for x in nums[:-1]:
        mx = max(mx, x)  # 更新最大值
        ans += mx  # 累加得分
    return ans

if __name__ == '__main__':
    nums = [1, 3, 1, 5]
    results = find_maximum_score(nums)
    print(results)

·

我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。 欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展