给定一个数组和一个和，找到最大长度小于总和的连续子阵列

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）时间。