Find the largest contiguous subarray such that a function of the elements in the subarray is less than the given value

Question

Question

I'm looking for an algorithm that can efficiently compute the largest allowable contiguous subarray where the function PowerUsed(subarray) is less than the parameter AllowedEnergy. Each element in the array contains two values, startingEnergyUsed and ContinuousEnergyUsed, and PowerUsed is computed given two arrays of the same size denoting the startingEnergy and continuousEnergy values associated with each element (example below). The solution needs to be better than O(n^2) time complexity, and ideally would be O(n) space complexity or less.

Given:

• std::vector startingEnergyUsed
• std::vector continuousEnergyUsed
• long AllowedEnergy

Constraints:

• startingEnergyUsed.size() == continuousEnergyUsed.size()
• 1 <= startingEnergyUsed.size() <= 2^32 - 1
• 0 <= startingEnergyUsed[i] <= 2^32 - 1
• 0 <= continuousEnergyUsed[i] <= 2^32 - 1
• PowerUsed(x) <= LONG_MAX for any subvector 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;

}

Additional details:

For reference, my current solution is the standard naïve O(n^2) solution involving iterating over each element and adding elements to it until the combined subvector exceeds AllowedEnergy and then trying again from the next element. I have minor improvements involving ignoring subarrays lower than my current max, but nothing that improves the big O time complexity.

The information I've provided is in C++ as that is what I've been using to work on the problem, but since this is an algorithm question I'm open to any solution based in procedural or object oriented languages.

Answer 1

Your PowerUsed function, given indices [L, R] representing subarray endpoints, breaks down into

max(StartingEnergyUsed[L, ... R]) 
+ (R - L + 1) * sum(ContinuousEnergyUsed[L, ... R])

Since all array values are positive, this function is monotonic with respect to subarray inclusion (i.e. expanding a subarray will never make the function smaller).

This means you can use a sliding window to find the maximum length in linear time, if you can maintain PowerUsed for your window in (amortized) constant time per operation as you add elements on the right of the window and remove them on the left. The sum can be maintained easily, the maximum needs a few more lines of code.

Since the sliding window is really a Queue, what you need is a Queue in which push_rear(), pop_front() and get_max() are all constant time operations. Technically that post asks for 'get_min', but taking any of the many existing answers there and replacing 'min' with 'max' will give you a Max-Queue with all amortized-constant-time operations.

A Max-Queue is just two double ended queues and a few lines of code. For example, here's a c++ Max-Queue implementation from modifying this answer:

#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();
}

Given that, here's pseudocode for your function. If you believe that the Max-Queue has constant time operations, this function must have linear complexity, since it's just a single loop from 0 to n with an (amortized) constant number of operations per iteration.

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;