-2

这是我的 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

对于 input1，我看不到应该是“110、-8、16”的预期答案。我尝试将返回语句更改为“maxSumIndex”而不是“maxSumIndex+1”。这打破了其他两个输入。

请提供您的想法

4

2 回答 2

1

有两个错误：

  1. maxSumIndex = i-k;应该是maxSumIndex = i-k+1;ik - 它是前一个数组的第一个索引，而不是当前最大的一个
  2. return maxSumIndex+1;return maxSumIndex;在索引 0 的情况下应该是其他方式（即前 3 个项目是最大的） - 你将返回 1，这是错误的
于 2016-03-24T18:03:15.620 回答
1

尝试这个：

        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;
于 2016-03-24T18:08:31.530 回答