尋找最小化數組其餘部分平均值的連續子序列？

假設有一個整數數組arr[0..n-1]。找到一個子序列sub[i..j]（i> 0和j < n - 1），這樣陣列的其餘部分的平均值最小。尋找最小化數組其餘部分平均值的連續子序列？

實施例：

arr[5] = {5,1,7,8,2};

刪除{7,8}，陣列變得{5, 1, 2}其具有平均2.67（最小可能的）。

我認爲這是對最長增長子序列的修改，但無法弄清楚。

謝謝，

來源

2016-01-17 user3813674

您還需要定義子序列的長度或剩餘元素的最小數量。例如，對您的示例更好的解決方案是刪除「{5，1，7，8}」並獲得平均值2（僅一個元素）。但是，如果您要求生成的數組需要兩個或多個元素，那麼這不是一個解決方案。 –

我忘記了我和j的條件。感謝您指出。 – user3813674

這仍然聽起來不對。 '{1}'平均爲'1'，其中'i = 1'，'j = 1'，'1> 0'和'1 <5-1' – Matt

我們使用二分搜索找到平均值。

假設，所有元素的那筆是S.

對於給定的x，讓我們檢查是否存在i和j，使得平均除了從i的所有元素的至j小於或等於x。

爲此，我們從arr中的所有元素中減去x。我們需要檢查是否存在i和j，使得除i之外的所有元素之和小於或等於零。爲此，我們找出當前數組中所有元素的總和：S'= S - x * n。所以我們想要找到i和j，使得從i到j的總和將大於或等於S'。要做到這一點，讓我們用大數和找到子數組。這可以使用優雅的Jay Kadane算法來完成：https://en.wikipedia.org/wiki/Maximum_subarray_problem

何時終止二分查找？當最大的子陣列和將爲零（或足夠接近）。

時間複雜度：O（n log w），w - 二進制搜索的精確位置。

來源

2016-01-17 04:22:39 SashaMN

尋找最小化數組其餘部分平均值的連續子序列？

回答

相關問題