问题标签 [divide-and-conquer]

我想用展示（n log n）的算法来实现最大子数组问题：

查找最大连续子数组，或数组中连续元素的最大总和。

假设：并非所有元素都是负数

我有一些可行的解决方案；问题在于重叠的中心数组，以及指定重叠子问题的适当索引，一些数组我得到了正确的答案，而另一些则没有。

只是为了比较和检查正确性，我实现了一个称为 Kadane 算法的解决方案（我相信复杂度是 Omega(n)）。

这是 Kandane 的算法（http://en.wikipedia.org/wiki/Maximum_subarray_problem）：

我的递归实现，使用分治法来比较子数组的最大值，然后对具有最大值的子数组进行递归调用，直到递归结束

结果：使用数组 subArrayProblem1 = {1, 2, 3, 4, 5, 6, 7, 8};

Kadane（int array []）：36 低：0 中：4 1,2,3,4,5,6,7,8,中：4 高：7 低中心：6 高中心：6

findMaxSubArray(int[] array, int lowIndex, int highIndex) global Max Range, low:7 high: 7 global Max Sum:36 BUILD SUCCESSFUL (总时间: 0 seconds)

问题尽管与 Kadane 相比，全局最大总和是正确的，但低指数和高指数范围反映了最后一次递归调用。

结果：使用数组 subArrayProblem = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97}；

Kadane（int数组[]）：1607低：0中：8 100,113,110,85,105,102,86,63,中+1：9高：16 101,94,106,101,79,94,90,97,lowCenter：16 highCenter：15

findMaxSubArray(int[] array, int lowIndex, int highIndex) global Max Range, low:16 high: 16 global Max Sum:1526

全局最大值不正确，注意区别其实是1个元素，也就是元素81

我正在尝试使用分治算法对链表进行洗牌，该算法在线性（n log n）时间和对数（log n）额外空间中随机洗牌链表。

我知道我可以做一个类似于可以在一个简单的值数组中使用的 Knuth shuffle，但我不确定如何通过分而治之的方式做到这一点。我的意思是，我实际上在划分什么？我是否只是划分到列表中的每个单独节点，然后使用一些随机值将列表随机组合在一起？

还是我给每个节点一个随机数，然后根据随机数对节点进行合并排序？

首先说我有一个问题，计算 10 亿位 Pi，计算一个大数的阶乘，或者对一个大列表执行合并排序。我想将问题分成更小的任务，并同时执行每个任务并组合结果。首先，这种类型的并发的名称是什么，您将如何在 Clojure 中实现它？

这个想法是递归地合并第一个 k/2 个列表和第二个 k/2 个列表，然后将两个合并的列表合并为一个列表并返回。

我对递归合并第一个 k/2 和第二个 k/2 列表意味着什么感到困惑。任何人都可以澄清这一点，或者可以查看一些解释这种递归的伪代码吗？

有人可以告诉如何生成 n 位字符串（所有可能的组合），即使用分而治之的方法从 0 到 2^n-1 计数位。

我可以使用以下算法做到这一点，但空间复杂度和时间复杂度都是 O(2^n)。有人可以给我一个更好的算法（使用分而治之），它需要比这更少的空间。

该程序的要点是使用蛮力方法（有效！）和分治法（无效）找到具有波动股票价格的一维数组的最大子数组。该程序的目的是找到天的集合（因此结构中的 lsub 和 rsub）和这些天的最大利润。

我在网上看到的所有地方，比如这个 powerpoint都表明我的代码应该可以工作。我也看到了类似的东西，但是在 StackOverflow 上的 Java 中，该代码的实现也不起作用。这是该 Java 程序的链接。

我的代码如下：

示例数据集：（它们应该在单独的行上，但它不允许我这样做。）

预期的输出是：

最大值为：43

左下标为：8

右下标是：11

我想为排列问题生成一个搜索树。我的要求如下：我想使用分而治之的策略来做到这一点

我正在给出一个示例树长度为 3 的排列。

合并排序是一种相当常见的排序算法，我已经编写了一个有效的合并排序算法。然后我想优化它。第一步是将它从递归转换为迭代，我这样做了。然后我无法辨别还有什么可以优化的。在浏览了互联网上的大量文章后，我得到了两种机制，使用多合并排序和平铺合并排序。然而，这些文档都没有提供任何伪代码，甚至都没有解释如何做到这一点，以及它如何提供作者所说的优势，比如缓存友好和改进的局部性命中。

任何人都可以详细说明这个问题，如果可能的话，提供一些伪代码？具体来说，我想知道如何使它对缓存友好。我完全不知道这些东西是什么，否则我会自己尝试的。

我到处读到，对于像Merge-Sortand这样的分而治Quicksort之的排序算法，与其递归直到只剩下一个元素，不如转移到Insertion-Sort达到某个阈值（比如 30 个元素）时。这很好，但为什么只有Insertion-Sort？为什么不Bubble-Sort或Selection-Sort，两者具有相似的O(N^2)性能？Insertion-Sort只有在对许多元素进行预排序时才应该派上用场（尽管这种优势也应该伴随着Bubble-Sort），但除此之外，为什么它应该比其他两个更有效？

其次，在这个链接上，在第二个答案及其随附的评论中，它说与upto a certainO(N log N)相比表现不佳。怎么来的？应该总是表现得比 差，因为对于所有 N >= 2，对吧？O(N^2)NN^2N log NN > log N

建议？

给定一个未排序的数组和元素的数量，对于每个元素，如果没有数字 -1，我必须打印其自身与数组中小于他的最远元素之间的元素数量

例子：

输入：10 6 10 3 9 15 输出：3 1 1 -1 -1 -1

我已经做到了，但是我的教授告诉我它可以做得更高效，当然我实际上在做 o(n^2)。分而治之？，二分查找？

我的解决方案：