Saturday, June 20, 2015

Maximum sub array of given length in linear time

 In this post I'm going to elaborate on a technique I used to calculate maximum sub array in linear time (fixed length maximum => max product).
  •  The below code iterate on the array as a normal loop iteration.
  •  In each iteration the loop variable product is taken and if it exceeds the maximum it is induced for a separate variable.
  • At the same time the number that was in the loop variable is queued into a separate array
  • As this continues the numbers that are completed will reach the maximum allowed sub array length. Now we should make sure next steps wont damage the fixed sub array length.
  • Now dequeue the queue and divide the maximum with the dequeued value and multiply with the next value in the iteration.
  • Continue this until the entire array is covered.

For the task two variables are required to save the temporary maximum value and the resultant value. Also the algorithm runs at O(n) time complexity.
The brute-force approach will require using loop within a loop and iterate over and over again requiring a huge computational power. Thus I have used this method in Euler 8 sum at Hackerrank :)

Special case where zeros contains has been handled in the main loop where the input is processed. Splitting with zeros and having strings lesser in length than required gives no useful results => more optimization to the algorithm ;)

Here is the code :)


No comments:

Post a Comment