Sunday, February 1, 2015

Sliding window implementation:

Problem: Given an array and subarray size, find the max. sum from subarrays.
Solution: 
Naive solution is to iterate through all the subarrays and find the sums. Each time, compare the sum with the previous max and update accordingly. The solution is quadratic in nature.
A better solution implementing sliding window where in each iteration, remove the first integer in the last array and add the value of the newly added array in the subarray.
An implementation of it is here in the link.

No comments:

Post a Comment