求解 MaxDouble Slice Kadane 的算法变体
Solving MaxDouble Slice Kadane's Algorithm Variation
我试图通过解决 Codality 问题来提高我的技能。我达到了这个：https://codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/
我实际上理论上理解了解决方案：
- 对数组使用 Kadane 算法并存储每个索引处的总和。
- 反转数组并做同样的事情。
- 通过一次一个地循环两个结果集来找到两者之和最大的点。
- 最大值为最大双切片。
我的问题不是如何解决问题。我的问题是关于人们如何想象这将是解决这个问题的方式。至少需要使用 3 个不同的概念：
如果数组中的所有元素都是正数或负数，这与数组中有一些正数和负数元素时的情况不同。
卡丹的算法
正向和反向遍历数组。
尽管如此，Codality 已将此问题标记为 "Painless"。
我的问题是我遗漏了什么吗？在不了解其中一些概念的情况下，我似乎很难解决这个问题。
有没有一种技术可以让我从头开始，从非常基本的概念开始，逐步了解解决此问题所需的概念。还是我在开始做题之前就应该了解这些概念？
我如何准备自己来解决这些我不知道未来所需概念的问题？
我认为你想多了，这就是为什么你觉得它比实际更难的原因：
The understanding that if all elements in the array are positive, or negative it is a different case than when there are some positive and negative elements in the array.
不必另当别论。您也许可以想出一个不关心这种区别并且仍然有效的算法。
您不需要从理解这个区别开始，所以在您必须或什至不得不考虑之前不要考虑它。
Kadane's Algorithm
不要想算法，想问题需要什么。通常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!"
我们的想法是在不改变其含义的情况下尽可能简化需求。然后你使用你的算法和演绎技能来找到解决方案。这些技能是随着时间和经验磨练出来的。
我试图通过解决 Codality 问题来提高我的技能。我达到了这个：https://codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/
我实际上理论上理解了解决方案：
- 对数组使用 Kadane 算法并存储每个索引处的总和。
- 反转数组并做同样的事情。
- 通过一次一个地循环两个结果集来找到两者之和最大的点。
- 最大值为最大双切片。
我的问题不是如何解决问题。我的问题是关于人们如何想象这将是解决这个问题的方式。至少需要使用 3 个不同的概念：
如果数组中的所有元素都是正数或负数，这与数组中有一些正数和负数元素时的情况不同。
卡丹的算法
正向和反向遍历数组。
尽管如此，Codality 已将此问题标记为 "Painless"。
我的问题是我遗漏了什么吗？在不了解其中一些概念的情况下，我似乎很难解决这个问题。
有没有一种技术可以让我从头开始，从非常基本的概念开始，逐步了解解决此问题所需的概念。还是我在开始做题之前就应该了解这些概念？
我如何准备自己来解决这些我不知道未来所需概念的问题？
我认为你想多了，这就是为什么你觉得它比实际更难的原因：
The understanding that if all elements in the array are positive, or negative it is a different case than when there are some positive and negative elements in the array.
不必另当别论。您也许可以想出一个不关心这种区别并且仍然有效的算法。
您不需要从理解这个区别开始，所以在您必须或什至不得不考虑之前不要考虑它。
Kadane's Algorithm
不要想算法，想问题需要什么。通常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!"
我们的想法是在不改变其含义的情况下尽可能简化需求。然后你使用你的算法和演绎技能来找到解决方案。这些技能是随着时间和经验磨练出来的。