題
我正在尋找一種可以有效計算最大允許連續子陣列的演算法，其中函式 PowerUsed(subarray) 小于引數 AllowedEnergy。陣列中的每個元素都包含兩個值，startingEnergyUsed 和 ContinuousEnergyUsed，并且 PowerUsed 是在給定兩個相同大小的陣列的情況下計算的，表示與每個元素關聯的startingEnergy 和 ContinuousEnergy 值（下面的示例）。解決方案需要優于 O(n^2) 時間復雜度，理想情況下應為 O(n) 空間復雜度或更小。
鑒于：
- std::vector 起始EnergyUsed
- std::vector 連續EnergyUsed
- 長允許能量
約束：
- startEnergyUsed.size() == ContinuousEnergyUsed.size()
- 1 <= startEnergyUsed.size() <= 2^32 - 1
- 0 <= startEnergyUsed[i] <= 2^32 - 1
- 0 <= 連續能源使用[i] <= 2^32 - 1
- PowerUsed(x) <= LONG_MAX 對于任何子向量 x
- 0 < AllowedEnergy <= LONG_MAX
long PowerUsed(std::vector<int> & StartingEnergyUsed, std::vector<int> & ContinuousEnergyUsed)
{
long powerUsed = std::max_element(StartingEnergyUsed.begin(), StartingEnergyUsed.end());
long totalContinuousEnergy = std::accumulate(ContinuousEnergyUsed.begin(),ContinuousEnergyUsed.end());
powerUsed = totalContinuousEnergy * ContinuousEnergyUsed.size();
return powerUsed;
}
額外細節：
作為參考，我當前的解決方案是標準的樸素 O(n^2) 解決方案，涉及迭代每個元素并向其添加元素，直到組合的子向量超過 AllowedEnergy，然后從下一個元素再次嘗試。我有一些小的改進，包括忽略低于我當前最大值的子陣列，但沒有什么能提高大 O 時間復雜度。
我提供的資訊是用 C 撰寫的，因為這是我一直用來解決這個問題的，但由于這是一個演算法問題，我對任何基于程序或面向物件語言的解決方案持開放態度。
uj5u.com熱心網友回復：
給定表示子陣列端點的索引，您的PowerUsed函式[L, R]分解為
max(StartingEnergyUsed[L, ... R])
(R - L 1) * sum(ContinuousEnergyUsed[L, ... R])
由于所有陣列值都是正數，因此該函式在子陣列包含方面是單調的（即擴展子陣列永遠不會使函式變小）。
這意味著您可以使用滑動視窗來找到線性時間的最大長度，如果您可以PowerUsed在每次操作中保持視窗的（攤銷）恒定時間，因為您在視窗右側添加元素并在左側洗掉它們。總和可以很容易地維護，最多需要幾行代碼。
由于滑動視窗實際上是一個Queue，所以你需要一個Queue，其中push_rear()、pop_front()和get_max()都是常數時間操作。從技術上講，該帖子要求提供“get_min”，但是從那里獲取許多現有答案中的任何一個并將“min”替換為“max”將為您提供一個包含所有攤銷常數時間操作的 Max-Queue。
Max-Queue 只是兩個雙端佇列和幾行代碼。例如，這是修改此答案的 c Max-Queue 實作：
#include <deque>
std::deque<int> main_queue;
std::deque<int> max_queue;
void PushRear(int elem)
{
main_queue.push(elem);
while(!max_queue.empty() && elem > max_queue.back())
{
max_queue.pop_back();
}
max_queue.push_back(elem);
}
void PopFront()
{
int elem = main_queue.front();
main_queue.pop();
if (elem == max_queue.front())
{
max_queue.pop_front();
}
}
int GetMax()
{
return max_queue.front();
}
鑒于此，這是您的函式的偽代碼。如果您認為 Max-Queue 具有恒定時間操作，則此函式必須具有線性復雜度，因為它只是一個回圈，0 to n每次迭代具有（攤銷）恒定數量的操作。
longest_length = 0;
left_index = 0;
window_sum = 0;
MaxQueue = new MaxQueue();
for (int right_index = 0; right_index < StartingEnergyUsed.size(); right_index = 1){
window_sum = ContinuousEnergyUsed[right_index];
MaxQueue.Push_Back(StartingEnergyUsed[right_index]);
if (window_sum * (right_index-left_index 1) MaxQueue.GetMax() >= AllowedEnergy){
window_sum -= ContinuousEnergyUsed[left_index];
MaxQueue.PopFront();
left_index = 1;
}
if (right_index-left_index 1 > longest_length &&
window_sum * (right_index-left_index 1) MaxQueue.GetMax() < AllowedEnergy) {
longest_length = right_index - left_index 1;
}
}
return longest_length;
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/438322.html
上一篇：ggplot2：不同寬度的條形圖