Optimizing an algorithm subtracting first elements from last elements

Question

I'm trying to optimize a slow part of a larger algorithm.

I have an array of random-looking numbers:

[295, 292, 208, 393, 394, 291, 182, 145, 175, 288, 71, 86, 396, 422]

(actual arrays are much longer), and an index: N (N = 5)

What I want to do is subtract subtract 1 from the last M elements for each of the first N elements that are smaller

So (pseudo-code):

for a = 1..5
  for b = 6..N
    if ary[a] < ary[b]
      ary[b]--;

Obviously this is a horribly inefficient O(N^2) algorithm. I'm trying to think of a faster way to do it, but can't. It seems like I should be able to pre-compute the values to subtract somehow, and reduce it to:

for a = 1..5
  // ???
for b = 6..N
  ary[b] -= ???

but I'm missing something.

[edit] I feel like an idiot. I didn't properly explain what I want, fixed.

Answer 1

Let's reorganize the loops:

for b = 6..N
  for a = 1..5
    if ary[a] < ary[b]
      ary[b] -= ary[a];

The result will be the same. But now the logic is more clear: from each element from the second part of array you subtract ary[1], then ary[2] and so on until some ary[a] is bigger that what remains from ary[b].

This can be optimized the following way. Calculate the cumulative sums of the first half of array: let sum[1]=ary[1], sum[2]=sum[1]+ary[2], sum[3]=sum[2]+ary[3], and so on. This can be done in O(N).

Now for each b you need to find such a_last that sum[a_last]<ary[b], but sum[a_last+1]>=ary[b] -- this will mean that from ary[b] you will subtract ary[1]+...+ary[a_last]=sum[a_last]. You can find such a_last using binary search in O(log N), thus making the overall algorithm O(N log N).

The pseudocode:

sum[0] = 0
for a = 1..5
    sum[a] = sum[a-1] + ary[a]
for b = 6..N
    a_last = maximal a such that sum[a]<ary[b] // use binary search
    ary[b] -= sum[a_last]