給定一個數組和一個和，找到最大長度小於總和的連續子陣列

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

如果我有更多的時間，我會寫邏輯內部具有用於清潔的方式循環，但這應該工作，它在，輸出工作（n）時間。