通过重排数组元素,使特定子数组和最大化?

如何通过重排数组元素使特定子数组的和最大化?

考虑这样的数组……【5,1,4,6,7】。

[5,1,4,6,7]

当我们选择一个index[0,2]来获取这个范围内的子数组总和,比如[5,1,4],我们得到的总和是10,但是如果我们重新排列数组,我们可以将这个总和最大化。

[5,7,6,1,4]

现在,我们已经将子数组索引[0,2]的和最大化为18。

我们可以对子数组指数进行许多查询,我们必须使其总和最大化。

我应该如何操作?有什么提示吗?

解决方案:

很明显,你的范围应该只包含数组中最大的元素。

因此,解决方案:对数组进行排序,计算排序后的数组所有前缀的总和。现在,如果你需要最大化长度为3的范围,答案是前3个数字的总和(已经在预处理中计算)。

这个解决方案在预处理中使用了O(n log n),回答每个查询需要O(1)。

给TA打赏
共{{data.count}}人
人已打赏
未分类

如何防止点击按钮后,在按钮旁边呈现一个新的组件。

2022-9-19 20:32:18

未分类

在多个字符串之间添加间隔的Regex。

2022-9-19 20:32:20

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索