Extracting maximum values from each of the subsets of an array
Single pass algorithm (~2n)

You can do it with a single pass over the array (which I shall denote as lst).


Maintain a maximum value (I shall denote this as max_val) once you hit a non-zero value. When we reach a zero, add (i, max_val) to the list of maximum values and reset the maximum value.
Build the new list using the list of maximum values.


This should give you pretty good performance (~2n since you iterate 2 times). However, if you need a parallel version...

Parallel algorithm

This is the first parallel algorithm I've ever designed, so pardon me if I screwed up somewhere. We use the MapReduce model which is quite simple to write.

Let k be the number of processes which you want to divide the work among and i be the number of each process where 0 &lt;= i &lt; k.

In the Map() procedure:


Each process starts at n/k * i indice and iterates till it hits n/k * (i+1).
Follow the algorithm as described in step 1 of the single pass algorithm.
If the first or last value is non-zero, it indicates that the values we have obtained may not be the maximum values of the subset as we may have only monitored a portion of the subset. Hence, we add it to the portions list.


When we flush, we mark the start and end indice that we have scanned and the maximum value, so as to indicate that we have not finished scanning that subarray.

For k = 3 and our array being [0, 0, 0, 0, 1] + [2, 3, 4, 0, 0] + [0, 2, 1, 0, 2] with a length of 15 (split into 3 segments for convenience):

i = 0: lst[0] = 0
       lst[1] = 0
       lst[2] = 0
       lst[3] = 0
       lst[4] = 1 # is_portion = True, max_val = 1
                  # add (4, 5, (4, 1)) to the list of portions
       return [] and [(4, 5, (4, 1))]
i = 1: lst[5] = 2 # is_portion = True, max_val = 2
       lst[6] = 3 # max_val = 3
       lst[7] = 4 # max_val = 4
       lst[8] = 0 # add (5, 8, (8, 4)) to the list of portions
       lst[9] = 0
       return [] and [(5, 8, (8, 4))]
i = 2: lst[10] = 0
       lst[11] = 2 # max_val = 2
       lst[12] = 1
       lst[13] = 0 # add (11, 2) to the list of maximum values
       lst[14] = 2 # is_portion = True, max_val = 2
                   # add (14, 15, (14, 2)) to the list of portions
       return [(11, 2)] and [(14, 15, (14, 2))]


In the Reduce() procedure, we merge the arrays we have together to form two lists:

1. Maximum values: [(11, 2)]
2. Portions not yet finished scanning: [(4, 5, (4, 1)), (5, 8, (8, 4)), (14, 15, (14, 2))]
  We merge the tuples (4, 5, (4, 1)) and (5, 8, (8, 4)) together and compare the maximum value found. (8, 4) &gt; (4, 1), so we get a maximum value (8, 4).
  The last tuple, (14, 15, (14, 2)), ends at the boundary of the array, so we immediately return the maximum value (14, 2).


We now get [(11, 2), (8, 4), (14, 2)]. We build the list using step 2 and we're done!

The time complexity should be around ~2n if you choose a good k value.