The window sliding algorithm is used to convert two nested loops (bruth force) into a single loop (linear), which means it enables us to reduce the time complexity from O(n²) to O(n).
The following is an example of converting the bruth force approach into the window sliding technique.
Given an array A = { 1, 3, 5, 6, 8, 10 }, find the maximum sum of 3 consecutive elements.
Bruth Force
int maxSum = 0;
for (int i = 0; i < A.size() - 3; i++)
{
int sum = 0;
for (int j = 0; j < 3 + 1; j++)
{
sum += A[i + j];
}
maxSum = max(sum, maxSum);
}
return maxSum;
Window Sliding
int maxSum = 0;
int panes = 0;
int windowSum = 0;
for (int i = 0; i < sizeA + 1; i++)
{
if (panes == 3)
{
maxSum = max(maxSum, windowSum);
windowSum -= A[i - 3];
panes--;
}
windowSum += A[i];
panes++;
}
'Algorithms' 카테고리의 다른 글
Dynamic Programming (DP) (0) | 2021.10.17 |
---|---|
Manacher's Algorithm (0) | 2021.09.12 |
Hopcroft-Karp algorithm (호프크로프트-카프) (0) | 2021.09.05 |
Breadth-first, Depth-first searches (BFS/DFS) (0) | 2021.09.03 |
Recursion vs. Iteration for Fibonacci (0) | 2021.08.25 |