How to solve a variation to the maximum subarray problem, so that the sum should be between two bounds?

Question

Let's say I have an array with integers, which represent the daily changes in the price of a stock, as an example the following array:

[3, -1, -4, 1, 5, -9, 2, 6]. 

How would I find the amount of subarrays which have a sum between two values (lower and upper, so l <= s <= u), such as -1 (=lower) and 0 (=upper)? In this case, the answer would be 5. You can have the subarrays

[3, -1, -4, 1]
[-1]
[-1, -4, 1, 5, -9, 2, 6]
[1, 5, -9, 2]
[-9, 2, 6]

Another example array would be:

[4, 2, 2, -6, 7] 

with lower bound 3, upper bound 4. The answer to this would be 3. I have tried the following very naïve approach, which I'm certain there are many faster alternatives for. I'm wondering how I can solve this problem faster, with divide-and-conquer or possibly through dynamically programming.

Class

public class Stock
{
   public int sequenceLength;
   public int[] prices;
   public int lowerBound;
   public int upperBound;
   public int count = 0;
   public Stock()
   {
      sequenceLength = Int32.Parse(Console.ReadLine());
      prices = new int[sequenceLength];
      var split = Console.ReadLine();
      var splitSpace = split.Split(' ');
      for (int i = 0; i < sequenceLength; i++)
         prices[i] = Int32.Parse(splitSpace[i]);
      lowerBound = Int32.Parse(Console.ReadLine());
      upperBound = Int32.Parse(Console.ReadLine());
   }
}

Usage

static void Main(string[] args)
{

   int testcases = Int32.Parse(Console.ReadLine());
   Stock[] stock = new Stock[testcases];

   for (int i = 0; i < testcases; i++)
      stock[i] = new Stock();

   int count = 0;
   for (int i = 0; i < stock.Length; i++)
   {
      for (int j = 0; j < stock[i].sequenceLength - 1; j++)
      {
         int sum = stock[i].prices[j];
         if (sum >= stock[i].lowerBound && sum <= stock[i].upperBound)
            count++;
         for (int k = j + 1; k < stock[i].sequenceLength; k++)
         {
            sum += stock[i].prices[k];
            if (sum >= stock[i].lowerBound && sum <= stock[i].upperBound)
               count++;
         }
      }
      if (stock[i].prices[stock[i].sequenceLength - 1] >= stock[i].lowerBound && stock[i].prices[stock[i].sequenceLength - 1] <= stock[i].upperBound)
         count++;
      stock[i].count = count;
      count = 0;
   }

   Console.Clear();
   for (int i = 0; i < stock.Length; i++)
      Console.WriteLine(stock[i].count);
}

Answer 1

There's already an answer with O(N^2) complexity, I'll propose a O(NlogN) solution.

Create an array sums, where sums[0] = array[0] and sums[i] = sums[i-1]+array[i]. Now, for each index i in sums, you need to find number of indexes j such that sums[i] - sums[j] is in range [lower, upper]. But how to find number of indexes j?

Create a balanced binary search tree (AVL tree). Insert sums[0] in it. Start processing nodes from left to right. After processing a node, add it to the tree. You can search for the number of indexes in range [lower, upper] in O(logN) complexity, and same applies for the insertion as well. That will give you a total time complexity of O(NlogN).

Answer 2

If I understand the problem (and the jury is out)

The premise is, the first loop works its way across the array. The second loop is in charge of keeping a sum and checking the range, then yielding the result

Obviously this is O(n²) time complexity

Given

public static IEnumerable<int[]> GetSubs(int[] source, int lower, int upper)
{
   for (var i = 0; i < source.Length; i++)
   for (int j = i, sum = 0; j < source.Length; j++)
   {
      sum += source[j];
      if (sum >= lower && sum <= upper)
         yield return source[i..(j+1)];
   }
}

Usage

var array = new[] { -5, -4, -3, -2, -1, 0, 2, 3, 4, 5, 6, 7, 8, 9 };

foreach (var sequence in GetSubs(array,2,5))
    Console.WriteLine($"{sequence.Sum()} : [{string.Join(", ", sequence)}]");
   

Output

5 : [-5, -4, -3, -2, -1, 0, 2, 3, 4, 5, 6]
4 : [-4, -3, -2, -1, 0, 2, 3, 4, 5]
3 : [-3, -2, -1, 0, 2, 3, 4]
2 : [-2, -1, 0, 2, 3]
4 : [-1, 0, 2, 3]
2 : [0, 2]
5 : [0, 2, 3]
2 : [2]
5 : [2, 3]
3 : [3]
4 : [4]
5 : [5]

Full Demo Here

_{Note : You could probably do this in linq with Enumerable.Range, however this is pretty easy to understand}

If you just wanted the count, you could remove the iterator all together, and just increment a counter when the if condition is true

public static int GetSubs(int[] source, int lower, int upper)
{
   var result = 0;
   for (var i = 0; i < source.Length; i++)
   for (int j = i, sum = 0; j < source.Length; j++)
   {
      sum+= source[j];
      if (sum >= lower && sum <= upper)
         result++;
   }
   return result;
}