解决MaxDouble Slice Kadane算法变体

Question

3

我试着通过解决Codality问题来提高我的技能。我遇到了这个问题: https://codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/ 我理论上了解解决方案:

1. 在数组上使用Kadane算法，并在每个索引处存储总和。 2. 反转数组并执行相同操作。 3. 通过循环遍历两个结果集中的一个来找到两者总和最大的点。 4. 最大值是最大双片段。

我的问题不是如何解决问题，而是如何想象这将是解决问题的方式。至少需要使用3个不同的概念:

1. 理解如果数组中的所有元素都是正数或负数，则与数组中有一些正数和负数的情况不同。 2. Kadane算法 3. 正向和反向遍历数组。

尽管如此，Codality将此问题标记为“轻松”。

我的问题是我错过了什么吗？似乎很难在不知道这些概念的情况下解决此问题。

是否有一种方法，可以从基础概念开始，并逐步掌握解决此问题所需的概念。还是说我需要在开始解决问题之前就知道这些概念？

如何准备自己以解决将来不知道所需概念的问题？

- Khoj Badami

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

我认为你想得太多了，这就是为什么你觉得它比实际困难:

如果数组中的所有元素都是正数或负数，则与数组中存在一些正数和负数元素时不同。

它不必是一个不同的情况。您可能能够想出一种算法，不关心这种区别，并且仍然可以工作。

您无需从理解此区别开始，因此在必要时甚至不要考虑它。

Kadane算法

不要考虑算法，而是考虑问题所需的内容。通常，可以用更少的内容来表达那个长长的10段落的问题陈述。

因此，让我们看看如何简化问题说明。

首先，将片段定义为三元组(x、y、z)。它被定义为从x + 1开始，以z-1结束并且不包含y的元素之和。

然后它要求最大和片段。如果我们需要最大片段，我们是否需要在定义中使用x和z？只要它为我们提供最大和，我们可能会让它从任何地方开始和结束，不是吗？

因此，将片段重新定义为数组的子集，它可以从任何地方开始，到达一些y-1，从y + 1继续并且在任何地方结束。更简单了，不是吗？

现在您需要最大的这样的片段。

现在，您可能认为您需要为每个y找到以y + 1开头的最大和子数组和以y-1结尾的最大和子数组。如果您可以找到这些内容，则可以为每个y更新全局最大值。

那么您如何做到这一点呢？这应该指向Kadane算法，它完成了您想要的一半内容：它计算以某个x结尾的最大和子数组。因此，如果您从两侧计算它，对于每个y，您只需要找到：

kadane(y - 1) + kadane_reverse(y + 1)

与全局最大值进行比较。

没有负数和正数的特殊情况。不要一看到问题就想“卡德恩算法(Kadane's!)”。

思路是尽可能简化需求，而不改变其含义。然后使用您的算法和推理技巧来达到解决方案。这些技能随着时间和经验的积累而得以锤炼。