window k 算法的最大和子数组未正确返回起始索引

Question

这是我的 maxSum 子数组代码

给定输入数组 -> [110,-4,3,6,7,11] 且 k =3，代码应给出 [110,-4,3]，因为这是具有最大总和的子数组.

我已经实现了算法。它适用于除一个输入之外的所有输入。我无法弄清楚出了什么问题。

public class MaxSumSizeK {


        private static int getMaxAvgSubarrayStartIndex(int input[], int k)
        {
            int n = input.length;
            if (k > n)
                throw new IllegalArgumentException("k should be less than or equal to n" );      
            if(k == n) {
                return 0;    
            }

            int sum = input[0];
            for (int i = 1; i < k; i++)
                sum += input[i];

            int maxSum = sum;
            int maxSumIndex = 0;

            for (int i = k; i < n; i++){
                sum = sum - input[i-k] + input[i] ;
                if (sum > maxSum){
                    maxSum = sum;
                    maxSumIndex = i-k;
                }
            }
            return maxSumIndex+1;
        }

        public static void printMaxAvgSubarray(int[] input, int k) {
            System.out.print("Maximum average subarray of length "  + k + " is:  " );
            int index = getMaxAvgSubarrayStartIndex(input, k);
            for(int i =0 ; i < k; i++) {
                System.out.print(input[index++] + " " );
            }
        }

        public static void main(String[] args) {
            int[] input = {11, -8, 16, -7, 24, -2, 300};
            int k = 3;
            printMaxAvgSubarray(input, k);
            System.out.println();
            int[] input1 = {110, -8, 16, -7, 24, -2, 3};
            printMaxAvgSubarray(input1, k);
            System.out.println();
            int[] input2 = {11, -8, 16, -7, 24, -2, 3};
            printMaxAvgSubarray(input2, k);
            System.out.println();
        }
    }

这是输出：

Maximum average subarray of length 3 is:  24 -2 300 
Maximum average subarray of length 3 is:  -8 16 -7 
Maximum average subarray of length 3 is:  16 -7 24

对于输入 1，我没有看到应为“110、-8、16”的预期答案。我尝试将 return 语句更改为 "maxSumIndex" 而不是 "maxSumIndex+1"。这会破坏其他两个输入。

请提供您的想法

Answer 1

有两个错误：

maxSumIndex = i-k; 应该是 maxSumIndex = i-k+1; i-k - 它是前一个数组的第一个索引，而不是当前最大的
return maxSumIndex+1; 应该是 return maxSumIndex; 否则在索引 0 的情况下（即前 3 项是最大的）- 你会 return 1，这是错误的

Answer 2

试试这个：

        int n = input.length;
        if (k > n)
            throw new IllegalArgumentException("k should be less than or equal to n" );
        if (k < 1)
            throw new IllegalArgumentException("k should be greater than 0" );      
        if(k == n) {
            return 0;    
        }

        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += input[i];

        int maxSum = sum;
        int maxSumIndex = 0;

        for (int j = 1; j < n-k; j++){
            sum = 0;
            for (int i = 0; i < k; i++){
                sum = sum + (int) Math.abs(input[i+j]);
            }
            if (sum > maxSum){
                maxSum = sum;
                maxSumIndex = i-k;
            }
        } 
        return maxSumIndex;

window k 算法的最大和子数组未正确返回起始索引

maximum sum subarray of window k algorithm not returning correctly for start index

java

arrays

algorithm

sub-array