前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2024-09-11:用go语言,给定一个从0开始的整数数组nums和一个正奇数整数k, 要求在nums数组中选择k个不重叠的子

2024-09-11:用go语言,给定一个从0开始的整数数组nums和一个正奇数整数k, 要求在nums数组中选择k个不重叠的子

作者头像
福大大架构师每日一题
发布2024-09-13 18:41:03
820
发布2024-09-13 18:41:03
举报
文章被收录于专栏:福大大架构师每日一题

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完整代码如下:

代码语言:javascript
复制
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)
}
}
returnint64(f[n])
}

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

Rust完整代码如下:

代码语言:javascript
复制
package main

import(
"fmt"
"math"
)

func maximumStrength(nums []int, k int) int64 {
    n :=len(nums)
    s :=make([]int, n+1)
fori, x := range nums {
        s[i+1]= s[i]+ x
}
    f :=make([]int, n+1)
fori:=1; i <= k; i++{
        pre := f[i-1]
        f[i-1]= math.MinInt
        mx := math.MinInt
        w :=(k - i +1)*(i%2*2-1)
forj:= 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)
}
}
returnint64(f[n])
}

func main(){
    nums :=[]int{1,2,3,-1,2}
    k :=3
    fmt.Println(maximumStrength(nums, k))
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2024-09-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 大体步骤如下:
  • Go完整代码如下:
  • Rust完整代码如下:
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档