-2

これがmaxSumサブアレイの私のコードです

入力配列 -> [110,-4,3,6,7,11] および k =3 が与えられた場合、コードは [110,-4,3] を与える必要があります。これは、最大合計を持つ部分配列であるためです。

アルゴリズムを実装しました。1 つを除くすべての入力に対して機能します。何が問題なのかわかりません。

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」であるはずの予想される答えが表示されません。return ステートメントを「maxSumIndex+1」ではなく「maxSumIndex」に変更してみました。これにより、他の 2 つの入力が中断されます。

親切にあなたの考えを提供してください

4

2 に答える 2

1

2 つのエラーがあります。

  1. maxSumIndex = i-k;ik である必要がありますmaxSumIndex = i-k+1;- これは前の配列の最初のインデックスであり、現在の最大のものではありません
  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 に答える