Ahmed Saleh Ahmed Saleh - 2 months ago 7
C++ Question

Sliding Maximum window brute force method

Given a large array of integers and a window of size 'w', find the current maximum in the window as the window slides through the entire array.

I have made two for loops, the first loops is working correctly but the inner loop doesn't move correctly based on different window sizes.

I tried to draw it on paper, but I still can't get a formula for the inner loop

int main() {

vector<int> arr = { -4, 2, -5, 3, 6 };
int window = 3;
for (int i = 0; i < arr.size() - window; i++)
{
int max = arr[i];
for (int j = i + 1; j < i + window; j++)
{
cout << " i = "<<i << "j = " << j << endl;

if (max < arr[j])
max = arr[j];
}

cout << max << " " << endl;

}

Answer

Your inner loop is correct. It's your outer loop's that's off by 1, it should be:

for (int i = 0; i <= arr.size() - window; i++)

With your array of 5 elements and the window size of 3, the last window is array[2] through array[4]. arr.size() is 5. window is 3. 5-3=2, and you need to still iterate for that window starting position.

Comments