关注
T4
T2的plus版,思想是一样的。两个长为n的数组,同位置元素可以交换。要求两数组各自的差值数组之和加起来最大,求最小的交换次数。首先注意我们的主要目标是差值数组之和最大,交换次数最小只是其次。同样使用动态规划,sums_n, sums_y分别表示末尾元素保持原位置和交换的情况下最大的差值数组之和,cnts_n, cnts_y对应二者的交换次数。设join_n, join_y分别是当前元素保持原位置和交换的情况下和上一个元素的差值之和,那么根据上一个元素是否交换,有转移方程
sums_n = max(sums_n + join_n, sums_y + join_y)
sums_y = max(sums_n + join_y, sums_y + join_n)
而cnts_n, cnts_y跟着赋值即可,如果括号里二者相等,在优先选择交换次数较小的。
注意sums_n/sums_y逻辑上同时计算,使用临时变量避免前者的计算影响后者。
时间复杂度O(n),空间复杂度O(1)。
查看原帖
点赞 3
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
2493次浏览 66人参与
# 刚工作,应该先搞钱or搞成长? #
20755次浏览 159人参与
# 牛客AI体验站 #
15489次浏览 275人参与
# 你觉得第一学历对求职有影响吗? #
229841次浏览 1266人参与
# 找工作中的小确幸 #
80331次浏览 448人参与
# 你觉得技术面多长时间合理? #
168032次浏览 1170人参与
# 实习在多还是在精 #
82681次浏览 509人参与
# 月薪多少能在一线城市生存 #
136339次浏览 898人参与
# 牛友的春节生活 #
11028次浏览 213人参与
# 备战春招/暑实,现在应该做什么? #
7523次浏览 199人参与
# 从夯到拉,锐评职场mentor #
7264次浏览 108人参与
# 实习到现在,你最困惑的一个问题 #
6538次浏览 164人参与
# 春招什么时候投? #
12890次浏览 208人参与
# 制造业的秋招小结 #
143306次浏览 2089人参与
# 电网笔面经互助 #
59646次浏览 476人参与
# 秋招踩过的“雷”,希望你别再踩 #
185625次浏览 1683人参与
# 春节提前走,你用什么理由请假? #
13155次浏览 288人参与
# 距离春招还有一个月,你现在是什么开局? #
9077次浏览 132人参与
# 今年秋招你收到了多少封邮件? #
38235次浏览 280人参与
# 暑期实习什么时候投? #
9276次浏览 197人参与