给定一个数组和一个和，求小于和的连续子数组的最大长度

Question

我有一个数组[1，2，3]，总和为4。所以所有的连续子数组都是 [1]，[1，2][2，3] 和 [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

这是经典最大连续子数组问题的变体。您可以使用动态规划（记忆）来解决这个问题。尝试这样做：

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

如果我有更多的时间，我会以更清晰的方式在for循环内部编写逻辑，但这应该有效，并且在O（n）时间内工作。