2024-09-11：用go语言，给定一个从0开始的整数数组nums和一个正奇数整数k， 要求在nums数组中选择k个不重叠的子数组， 使得这些子数组的能量值之和最大。 子数组的能量值是通过一定规则计

2024-09-11：用go语言，给定一个从0开始的整数数组nums和一个正奇数整数k，

要求在nums数组中选择k个不重叠的子数组，

使得这些子数组的能量值之和最大。

子数组的能量值是通过一定规则计算得到的，

具体规则是对于某个子数组，将其每个元素乘以一个特定系数，

并将这些结果相加，系数随着元素在子数组中位置的变化而变化。

最终，要求找到一组k个不重叠的子数组，使得这些子数组的能量值之和达到最大值。

需要注意的是，选择的子数组不需要覆盖整个原始数组。

最后要返回能够获得的最大能量值。

输入：nums = [1,2,3,-1,2], k = 3。

输出：22。

解释：选择 3 个子数组的最好方式是选择：nums[0..2] ，nums[3..3] 和 nums[4..4] 。能量值为 (1 + 2 + 3) * 3 - (-1) * 2 + 2 * 1 = 22 。

答案2024-09-11：

chatgpt

题目来自leetcode3077。

大体步骤如下：

1.创建长度为 n+1 的累积和数组 s，其中 s[i] 存储前 i 个元素的和。

2.创建长度为 n+1 的数组 f，用于存放最大能量值累积。

3.循环k次，表示每次选择一个子数组的过程：

3.a.初始化 pre 为 f[i-1]，f[i-1] 为负无穷大，设置初始最大值为负无穷大，定义一个权重 w。

3.b.从第 i 个位置开始循环到 n-k+i 位置，计算每次选择一个子数组后的最大能量值，并更新 f[j]。

4.返回最终的最大能量值 f[n]。

总的时间复杂度为 O(n*k)，其中 n 为数组的长度。

总的额外空间复杂度为 O(n)，主要由额外创建的两个长度为 n+1 的数组所占据。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func maximumStrength(nums []int, k int) int64 {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	f := make([]int, n+1)
	for i := 1; i <= k; i++ {
		pre := f[i-1]
		f[i-1] = math.MinInt
		mx := math.MinInt
		w := (k - i + 1) * (i%2*2 - 1)
		for j := i; j <= n-k+i; j++ {
			mx = max(mx, pre-s[j-1]*w)
			pre = f[j]
			f[j] = max(f[j-1], s[j]*w+mx)
		}
	}
	return int64(f[n])
}

func main() {
	nums := []int{1, 2, 3, -1, 2}
	k := 3
	fmt.Println(maximumStrength(nums, k))
}

Rust完整代码如下：

package main

import (
	"fmt"
	"math"
)

func maximumStrength(nums []int, k int) int64 {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	f := make([]int, n+1)
	for i := 1; i <= k; i++ {
		pre := f[i-1]
		f[i-1] = math.MinInt
		mx := math.MinInt
		w := (k - i + 1) * (i%2*2 - 1)
		for j := i; j <= n-k+i; j++ {
			mx = max(mx, pre-s[j-1]*w)
			pre = f[j]
			f[j] = max(f[j-1], s[j]*w+mx)
		}
	}
	return int64(f[n])
}

func main() {
	nums := []int{1, 2, 3, -1, 2}
	k := 3
	fmt.Println(maximumStrength(nums, k))
}