问题标签 [prefix-sum]

我正在尝试使用 CUDA 实现总和减少，但是我希望减少在右边而不是在左边。我写了下面的代码，但我不知道为什么它不起作用

任何想法我做错了什么？

我一直在解决算法问题，我对这些术语有点困惑。

当我们想像下面的代码那样计算前缀和（或累积和）时，我们可以说我们正在使用动态规划吗？

根据此页面中的定义，

动态规划用于我们有问题的地方，可以将其划分为类似的子问题，以便可以重用它们的结果。

在我的prefix_sum算法中，将当前的计算（prefix_sum[i]）分成类似的子问题（prefix_sum[i - 1] + nums[i - 1]），这样之前的结果（prefix_sum[i - 1]）就可以被重复使用。所以我假设计算前缀和是动态规划的应用之一。

我可以说它是动态编程，还是应该使用不同的术语？（特别是在思考编码面试的情况。）

我一直在 leetcode 上尝试这个问题。238. 除自身以外的数组的乘积

给定一个整数数组nums，返回一个数组 answer，使得 answer[i]等于nums除了 nums[i]之外的所有元素的乘积。

nums 的任何前缀或后缀的乘积都保证适合 32 位整数。

您必须编写一个在O(n)时间内运行且不使用除法运算的算法。

示例 1：

示例 2：

这是我对上述问题的解决方案。

这是通过 19/20 测试用例。有一个测试用例不起作用，我收到错误“超出时间限制”。

下面给出了失败的测试用例：

如果有人可以帮助我对我的代码做哪个版本？

输出：1 END 32 END 1 4 END 16 END 32 END 16 0 END 1 2 6 7 END 1267

所以我知道部分递归和由于前半部分的 32 而被弄乱了。但我目前正在努力寻找原因。初始算法使用从 1 到 n 的数组。它与范围有关吗？

谢谢你的帮助。

编辑：

现在我得到：

1 2 结束 6684773 7864425 结束 1 2 3 7 结束 1237

是什么导致无法计算前缀和？

现在解决了：

在 C++ 中，有一个std::partial_sum计算前缀和的函数。编码

将覆盖 a to 1 3 6 10 15，这是预期的。

但是，在大多数情况下，我想使用前缀总和，我希望0前面有一个表示“空总和”，以便我可以a[2] - a[0]用来查询前两个元素的总和。（这允许我使用一个简单的嵌套 for 循环来查找所有子数组的总和）。有没有办法用函数来实现它std::partial_sum？我不知道这是否可能，因为输出大小将是输入大小 + 1。

注意：我不是在寻找a预先改变内容或类型的方法。

如果大小a是一个问题：

像这样的东西也可以为我工作。

在 Haskell 中计算前缀和的简单方法是

产生输出

我需要写逆，这就是我想出的：

这似乎是正确的（但我可能错过了一些东西）。有没有更简单或更有效的方法来做到这一点，可能使用扫描？

我最近在做这个问题，直接取自IOI 2010的第3天任务3，“生活质量”，我遇到了一个奇怪的现象。

我正在设置一个 0-1 矩阵并使用它来计算 1 个循环中的前缀和矩阵：

我在 4 次测试中获得了 TLE（超出时间限制）（时间限制为 2.0 秒）。分别使用 2 for 循环时：

给了我完整的交流电（接受）。

从这里的4张图片中我们可以看到：

• TLE 结果，图 1：https ://i.stack.imgur.com/9o5C2.png

• TLE 结果，图 2：https ://i.stack.imgur.com/TJwX5.png

• AC结果，图1：https ://i.stack.imgur.com/1fo2H.png

• AC结果，图2：https ://i.stack.imgur.com/CSsZ2.png

2 个 for 循环代码通常运行得更快一些（即使在接受的测试用例中），这与我认为单个 for 循环应该更快的逻辑形成鲜明对比。为什么会这样？

完整代码（AC）：https ://pastebin.com/c7at11Ha （请忽略所有废话和类似的东西using namespace std;，因为这是一场竞争性编程比赛）。

• 注：评委服务器lqdoj.edu.vn建立在全球编程竞赛平台dmoj.ca之上。

给出一个整数数组，例如： 10, -10, -1, -1, 10 。我必须找到最小的重新分配，使得数组的所有前缀总和> = 0。假定数组中所有元素的总和
为非负数。在上面的示例中，我们可以将 -10 移动到数组的末尾以使所有前缀和为正。不知道如何有效地解决这个问题。取一个数字并将其插入其他任何地方将被视为一次重新分配。该问题将通过另一种类型的重新分配来解决：

1. 任何负数都可以移动到数组的末尾

最近我遇到了一个似乎很有趣的游戏，它建议在大型数据集上同时实现两指针和前缀和技术。这是任务本身：

想象有一个长度为k的数组v ，其中k (k<=10**5) 表示由两个数字组成的条目数量：A（所谓的堆）和N（数量），例如：

A ( v[i][0]) 是值，N ( v[i][1]) 是给出该值的次数。换句话说，N是A的频率。

现在，我们要做的是选择最小的 A，从列表的两端开始，从当前位置减去它，然后将它添加到后面的位置。然后我们继续这样做，直到中间只剩下两个或一个etries。换句话说，每一步我们选择最小的一堆，然后从两端减去它，直到剩下一两堆。

答案应该包括两行：第一行包含“1”或“2”，具体取决于剩余的桩数，第二行是结果本身。

为简化起见，我们可以将堆表示为如下所示的普通列表：

我们从左端和右端（2）中选择最小值，减去它并添加到下一个值：

4 和 5 的最小值是 4，所以我们减去 4 得到两堆。

输出是：

我的代码是：

该解决方案在k = 10**5时未能达到时间限制（2 秒），因为它需要将数组转换为普通列表，并且几乎不使用前缀和。我确信有一个更快的解决方案，它带有前缀和、附加变量和存储一个给定的数组。对于如何加快此代码的任何建议，我将不胜感激。
为防止任何与语言相关的评论：该游戏适用于任何编程语言，因此时间限制不是专门针对 python 的问题。

问题：给定一个整数数组 A，求 j - i 在 A[i] <= A[j] 约束下的最大值。

如果没有可能的解决方案，则返回 -1。

例子 ：

A : [3 5 4 2] 输出 : 2 对 (3, 4)

输入： 9 8 7 -9 -1

预期输出： 1

我的输出： 0

除了上面给定的输入之外，我尝试的代码适用于所有情况，谁能解释为什么它会失败并为我提供更正的版本？

我的代码（Python）：

我尝试使用 2 个循环，它通过了上述情况，但为另一个提供了 Time Limit Exceed。