2

我试图通过解决 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 还是将此问题标记为“无痛”。

我的问题是我错过了什么吗？在不了解其中一些概念的情况下，我似乎很难解决这个问题。

有没有一种技术可以让我从头开始和非常基本的概念，然后逐步达到解决这个问题所需的概念。还是在开始问题之前我就应该知道这些概念？

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

4

1 回答 1

2

我认为您对问题的思考过度了，这就是为什么您发现它比它更困难的原因：

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

不必是不同的情况。您可能会想出一个不关心这种区别并且无论如何都可以工作的算法。

你不需要从理解这个区别开始，所以在你必须要考虑之前不要考虑它。

Kadane 算法

不要想算法，想问题需要什么。通常，10+ 段的问题陈述可以用更少的方式表达。

因此，让我们看看如何简化问题陈述。

它首先将切片定义为三元组(x, y, z)。它定义为从 开始x+1、结束于z-1且不包含的元素的总和y。

然后它要求最大和切片。如果我们需要最大切片，我们是否需要x和z在定义中？我们不妨让它在任何地方开始和结束，只要它能让我们得到最大的总和，不是吗？

因此，将切片重新定义为数组的子集，该数组从任何地方开始，一直到 some y-1，从任何地方继续y+1并结束。简单多了，不是吗？

现在您需要最大的此类切片。

现在您可能会认为，对于每个y，您需要从 开始y+1的最大和子数组和以 结束的最大和子数组y-1。如果你能找到这些，你可以为每个更新一个全局最大值y。

那么你是怎么做到的呢？现在，这应该将您指向 Kadane 的算法，它完成了您想要的一半：它计算以 some 结尾的最大 sum 子数组x。所以如果你从两边计算它，对于 each y，你只需要找到：

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

并与全局最大值进行比较。

负面和正面没有特殊情况。没有想到“Kadane的！” 一旦你看到问题。

这个想法是在不改变其含义的情况下尽可能地简化需求。然后你使用你的算法和演绎技巧来找到一个解决方案。这些技能是经过时间和经验磨练出来的。

于 2017-02-14T09:16:40.647 回答