解決MaxDouble切片Kadane的算法變化

Question

我試圖通過解決Codality問題來提高我的技能。我達到了這個一個：https://codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

我其實理論上百思不得其解：

1. 使用Kadane的算法的陣列和存儲和各項指標的。
2. 顛倒數組並執行相同操作。
3. 通過一次循環兩個結果集來找出兩者之和的最大值。
4. 最大值是最大雙切片。

我的問題不在於如何解決問題。我的問題是關於如何設想這將成爲解決這個問題的方法。有跡象表明，需要進行使用的AT-至少3級不同的概念：

1. 的理解是，如果該數組中的所有元素都爲正，或負的這是一個不同的情況下，當有一些正和負比數組中的元素。

2. Kadane的算法

3. 去陣列上向前和扭轉。

儘管如此，Codality已將此問題標記爲「無痛」。

我的問題是我錯過了什麼？我很難在不知道這些概念的情況下解決這個問題。

有沒有一種技術，我可以從頭開始，非常基本的概念，並根據解決這個問題所需的概念。還是在開始解決問題之前，我期望知道這些概念？

我該如何準備我的自我解決這些問題，因爲我不知道未來需要的概念？

Answer 1

我認爲你得太多的問題，這就是爲什麼你會發現它更困難比是：

的理解是，如果陣列中的所有元素都爲正，或負這是一個不同的情況下比當數組中有一些正面和負面的元素。

它不一定是不同的情況。你可能會想出一個不關心這個區別的算法，並且無論如何都可以工作。

你不需要從理解這個區別開始，所以不要直到或者你必須考慮它。

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) 

並配有全球最大比較。

沒有特殊的負面和正面情況。沒想到「卡丹的！」只要你看到問題。

這個想法是儘可能簡化要求而不改變其含義。然後你使用算法和演繹技巧來達成解決方案。隨着時間和經驗磨練這些技能。