配列と合計を指定すると、最大長連続サブアレイが合計よりも小さい

Question

配列[1,2,3]を持ち、合計を4とします。したがって、すべての連続サブ配列は[1]、[1、 2] [2,3] ans [1,2,3]。したがって、合計以下の最大長さのサブアレイは[1,2]で、長さは2です。

すべてのサブアレイを見つけて。しかし、このアプローチは負の数では機能しません。 {1,2,1,1,3、-2、-3,7,9}; - 回答：7

private static void maximumSubArray(int[] a, int sum) { 

    int start = 0; 
    int end =0; 
    int mylen =-1; 
    int subarrSum =0; 
    for(int i=0;i<a.length;i++){ 
     subarrSum += a[i]; 
     end++; 
     while(subarrSum > sum){ 
      subarrSum-= a[start]; 
      start +=1; 

     } 

     mylen = Math.max(mylen, end-start); 
    } 
    System.out.println(mylen + " -- My len"); 

} 

Answer 1

これは古典的なmaximum contiguous subarray problemのバリエーションです。 dynamic programming（暗記）を使用してこの問題を解決することができます。このような何かを試してみてください：私はいくつかのより多くの時間を持っていた場合

private static void maximumSubArray(int[] a, long sum, int maxLen) { 
    long maximumSoFar = Long.MIN_VALUE; 
    long maximumEndingHere = Long.MIN_VALUE; 
    for (int i = 0; i < a.length; i++) { 
     // if you're inside the array beyond maxLen, start dropping off the previous start element 
     int prevStart = i >= maxLen ? a[i - maxLen] : 0; 
     maximumEndingHere = Math.max(a[i], maximumEndingHere + a[i] - prevStart); 
     if (maximumEndingHere > maximumSoFar && maximumEndingHere <= sum) { 
      maximumSoFar = maximumEndingHere; 
     } else if (a[i] > maximumSoFar && a[i] <= sum) { 
      maximumSoFar = a[i]; 
     } else if (maximumEndingHere > sum) { 
      maximumEndingHere -= prevStart; 
     } 
    } 
    System.out.println(maximumSoFar); 
} 

、私はクリーンな方法でループのための内部のロジックを記述しますが、これは動作するはずですし、それはO（n）の時間で動作します。