使用滑动 Window 方法找到最大的连续子数组

Question

我对滑动 window 问题有点困惑，问题陈述相对简单，给定参数 k，其中 k 是 window 的大小，找到可能的最大总和。

例如

array[] = {4,2,1,7,8,1,2,7,1,0} k = 3,最大连续子数组为{7,8,1}等于到 16

我有代码，但是我有一行没看懂

 *public static int findMaxSumSubarray(int[] arr, int k)
{
 int currentSum = 0;
 int max = Integer.MIN_VALUE;
 for(int i = 0; i<arr.length;++i)
 {
     currentSum += arr[i];
    

     /*
     lets take an array example  let arr = {4,2,1,7,8,1,2,7,1,0}
     when i is at k-1 then we have effectively covered a valid subset, lets say
     k = 3, when i moves to  the third element which is 1, a valid subset has been 
     covered
      */
     
       if(i >= k - 1)
     {
          max = Math.max(max,currentSum);
          currentSum -= arr[i - (k-1)];
     }
 }
 return  max;
}**

我不太明白的那一行是currentSum -= arr[i-(k-1)]

有人可以提供一张小桌子吗check/example 将不胜感激

我的理解

让我们使用之前的数组 = {4,2,1,7,8,1,2,7,1,0}

我们将迭代直到索引 2 处的元素，我们得到 4+2+1，因此我们已经覆盖了一个有效的 window 大小，完成后，编译器将转到 if 语句，由于 i 明显小于或等于 k-1 我们将执行此块。

currentSum -= arr[i - (k-1)]; 这里发生了什么？

提前对格式表示歉意，感谢所有这些回答。

Answer 1

if(i >= k - 1)

此检查是为了确保 sum 变量始终具有 k 个元素的总和。如果 window 大小是 k，那么一切都很好。然后移动到下一个 i 时大小变为 k+1。现在，sum 具有 k+1 个元素的值，因此您从 sum 的最后一个 window 中删除 的第一个元素以使 sum 具有又是 k 个元素的总和。请参阅下图以更清楚地了解 k = 3。

正如您在上图中看到的，对于大小为 k 的每个 下一个 window，我们必须删除前一个 window在 currentSum -= arr[i - (k-1)];
中完成的第一个元素

使用滑动 Window 方法找到最大的连续子数组

Find the Largest Contingous Sub Array using the Sliding Window Approach

arrays

algorithm

optimization

sliding-window