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

Question

Here is my code for maxSum subarray

given input array -> [110,-4,3,6,7,11] and k =3, the code should give [110,-4,3] since that is the subarray which has maximum sum.

I have implemented the algorithm. it works for all the input except one. I am unable to figure out what is going wrong.

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();
        }
    }

Here is the output:

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 

for input1, I do not see the expected answer which should be "110, -8, 16". I tried changing the return statement to "maxSumIndex" instead of "maxSumIndex+1". that breaks the other two inputs.

kindly provide your thoughs

Answer 1

there are two errors:

1. maxSumIndex = i-k; should be maxSumIndex = i-k+1; i-k - it is first index of previous array, not current maximal one
2. return maxSumIndex+1; should be return maxSumIndex; otherway in case of index 0 (ie first 3 items are maximal) - you will return 1, which is wrong