슬라이딩 윈도우

배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘.

ex. 정수로 이루어진 배열[2, 4, 7, 10, 8, 4, 5, 6, 7, 1]에서 길이가 3인 서브배열의 합계가 가장 큰 서브배열은?

특정 길이의 하위 배열의 최대 합계 값을 구하는 단순한 방식 살펴보기
for루프로 모든 배열 요소를 특정 길이만큼 순회하며 합계를 구해서 최대값을 구하는 단순하고 비효율적인 방식

코드가 짧으면 문제없지만 더 효율적으로 작성할 수 있다.
중복요소를 재사용하자
-> 슬라이딩 윈도우 알고리즘의 핵심

코드

package StringSorting;

public class SlidingWindow {
    public static void main(String[] args) {
        int[] arr = {2, 4, 7, 10, 8, 4};
//        int[] arr = {2, 4, 7, 10, 8, 4, 5, 6, 7, 1};
        int n = 3;
        System.out.println(reuse(arr, n));

//        int maxSum = 0, curSum;
//
//        for (int i = 0; i < arr.length - n + 1; i++) {
//            curSum = arr[i] + arr[i + 1] + arr[i + 2];
//            maxSum = Math.max(maxSum, curSum);
//        }
//        System.out.println(maxSum);
    }

    static int reuse(int[] arr, int k) {
        int windowSum = 0, windowStart = 0, maxSum = 0;

        for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
            windowSum += arr[windowEnd];

            if (windowEnd - windowStart >= k - 1) {
                maxSum = Math.max(maxSum, windowSum);
                windowSum -= arr[windowStart++];
            }
        }
        return maxSum;
    }
}

참고