maksimum toplamı altdizilim

Question

İşte maxSum benim kod

verilen giriş dizisi

altdizilim olan başlangıç ​​endeksi için doğru dönen değil , kod [110, -4,3] vermelidir, çünkü bu maksimum toplamı olan alt dizidir.

Ben algoritması uyguladık. Biri hariç tüm girdiler için çalışır. Neyin yanlış gittiğini anlayamıyorum.

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 için ben olmalı beklenen cevabı "110, -8, 16" görmüyorum: Burada

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

çıkıştır. Dönüş ifadesini "maxSumIndex + 1" yerine "maxSumIndex" olarak değiştirmeyi denedim. diğer iki girişi kırıyor.

nazik

Answer 1

iki hata olduğunda sizin thoughs sağlar:

1. maxSumIndex = i-k;maxSumIndex = i-k+1; ik olmalıdır - bu bir önceki dizinin ilk endeks,
2. return maxSumIndex+1; içinde return maxSumIndex; otherway olmalıdır biri değil şimdiki maksimaldir indeksi 0 (yani ilk 3 ürün maksimal vardır) vaka - yanlış sen 1 dönecektir

Answer 2

Bunu deneyin:

 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;