问题
我正在寻找一种算法，它可以有效地计算最大允许的连续子数组，其中函数PowerUsed(subarray(小于参数AllowedEnergy。数组中的每个元素都包含两个值，startingEnergyUsed和ContinuousEnergyUseed，给定两个相同大小的数组来计算PowerUsed，这两个数组表示与每个元素关联的startingEnergy和continuousEnergy值(以下示例(。解决方案需要比O(n^2(时间复杂度更好，理想情况下是O(n(空间复杂度或更低。
给定：
- 标准：：矢量启动已用能量
- std:：vector continuousEnergyUsed
- 长期允许能量
限制：
- startingEnergyUsed.size((==continuousEnergyUsed.size((
- 1<=startingEnergyUsed.size((<=2^32-1
- 0<=startingEnergyUsed[i]<=2^32-1
- 0<=continuousEnergyUsed[i]<=2^32-1
- PowerUsed(x(<=任何子向量x的LONG_MAX
- 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++编写的，因为这是我用来解决这个问题的，但由于这是一个算法问题，我对任何基于过程或面向对象语言的解决方案都持开放态度。
您的PowerUsed函数，给定表示子阵列端点的索引[L, R]，分解为
max(StartingEnergyUsed[L, ... R])
+ (R - L + 1) * sum(ContinuousEnergyUsed[L, ... R])
由于所有数组值都是正的，因此该函数相对于子数组包含是单调的(即，扩展子数组永远不会使函数变小(。
这意味着，如果在窗口右侧添加元素并在左侧删除元素时，每次操作都能在(摊销(恒定时间内保持窗口的PowerUsed，则可以使用滑动窗口来查找线性时间中的最大长度。总和可以很容易地维护，最大值需要几行代码。
由于滑动窗口实际上是一个Queue，所以您需要的是一个其中push_rear((、pop_front((和get_max((都是恒定时间操作的Queue。从技术上讲，这篇文章要求"get_min"，但从现有的许多答案中选择任何一个，并将"min"替换为"max"，将为您提供一个包含所有摊销恒定时间操作的max Queue。
最大队列只是两个双端队列和几行代码。例如，这里有一个通过修改这个答案实现的c++最大队列：
#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;