修正滑动窗

Question

最近，我在一次面试中被问到一个问题，这个问题是数组中k大小的连续和的修改版本。所以问题是这样的:给出数组a中k元素的最大连续和。我们只能从开始或结束选择k元素，或者从开始选择k-1元素，从开始选择1元素，从开始选择k-2元素，从开始选择2元素，从结束选择k-2元素，从结束选择k-2元素。例如：

[5,-2,3,1,2]
k=3

o/p:8

all possible combinations:[5,-2,3],[3,1,2][5,2,1],[-2,5,2]
max sum combinations: [5,2,1], etc

有人能用java解释逻辑吗。

Answer 1

这是我一次测试的结果。

Input array   [5, -2, 3, 1, 2]
Window length 3
Current window  [5, -2, 3]
Sum of current window 6
Current window  [-2, 3, 1]
Sum of current window 2
Current window  [3, 1, 2]
Sum of current window 6
Current window  [1, 2, 5]
Sum of current window 8
Current window  [2, 5, -2]
Sum of current window 5
Maximum sum   8

使用环绕滑动窗口，输入数组中的窗口与值完全相同。只要窗口长度小于数组的长度，窗口长度就无关紧要。

“诀窍”是确保数组下标始终小于数组的长度。因此，我们使用余数(%)运算符来确保数组索引始终在0和array.length -1之间；

这是完整的可运行代码。尝试使用不同的数组和不同的窗口长度。

import java.util.Arrays;

public class WrapAroundSlidingWindow {

    public static void main(String[] args) {
        WrapAroundSlidingWindow wasw = new WrapAroundSlidingWindow();
        
        int[] array = { 5, -2, 3, 1, 2 };
        int k = 3;
        System.out.println("Input array   " + Arrays.toString(array));
        System.out.println("Window length " + k);
        System.out.println("Maximum sum   " + wasw.calculateMaximumSum(array, k));
    }
    
    public int calculateMaximumSum(int[] array, int windowLength) {
        int maximumSum = calculateSum(array, 0, windowLength);
        System.out.println("Sum of current window " + maximumSum);
        
        for (int index = 1; index < array.length; index++) {
            int sum = calculateSum(array, index, windowLength);
            System.out.println("Sum of current window " + sum);
            maximumSum = Math.max(maximumSum, sum);
        }
        
        return maximumSum;
    }
    
    private int calculateSum(int[] array, int startIndex, int windowLength) {
        int sum = 0;
        System.out.print("Current window  [");
        
        for (int index = 0; index < windowLength; index++) {
            int jndex = (startIndex + index) % array.length;
            System.out.print(array[jndex]);
            if (index < windowLength - 1) {
                System.out.print(", ");
            }
            sum += array[jndex];
        }
        System.out.println("]");
        
        return sum;
    }

}