最大的子陣列變化

Question

我必須解決一個問題，就像最大的子陣列問題。我必須找到平均值大於k的最大子陣列。我想到了以下技巧。我可以將大小爲n的數組A []轉換爲B []，其中B [i] = A [i] -k。所以現在平均值必須> 0。但是大於零的平均值不僅僅意味着總和大於零？所以我可以直接應用Kadane的算法。我對嗎？ （總是在約束下，有1個正值）

Answer 1

不，kadane的算法仍然會找到你的最大和的子陣列...我必須解決同樣的問題。到目前爲止，我發現如果我們像上面提到的那樣創建數組B，然後創建包含數組B的部分和的數組C，那麼我們查找的最大間隔（i，j）具有相同的數字爲我和j！例如：

陣列A是：1 10 -1 -1 4 -1 7 2 8 1 .....並且給定k是5然後 陣列B是：-4 5 -6 -6 -1 -6 2 -3 3 -4 array C是：-4 1 -5 -11 -12 -18 -16 -19 -16 -20 所以我們要找的子數組是[7,2,8]，長度爲3，並且具有相同的第一個和最後一個元素，即-16 !!!!我忘了告訴我們正在尋找一個O（n）或O（n * logn）算法.... @lets_solve_it你是對的，但你的算法是O（n^2）whitch是對於我們想要處理的數據來說，這種方式很重要。我接近用C++中的函數圖解決它，這就像一個哈希表。我這是正確的方向，因爲這裏數組C的元素與它們的索引有直接關係！另外，我們的教授告訴我們，另一個可能的解決方案是再次製作數組C，然後採用（特殊的）數據透視進行快速排序......但我不完全明白我們期望從快速排序中做什麼。

Answer 2

@ panos7：

已創建後陣列C（部分和陣列上），尋求C，Ci和Cj的兩個值，

使得，CJ> =次，和，（ジ）儘可能「大」。 （j-i）→MAX。

然後返回j-i。

在你的榜樣，-16> = - 18，所以你返回J-11 = 9-6 = 3

這是正確的答案！