最大的连续子数组之和不大于k。

For example, we have

例如,我们有

{2,2,-1}, 
when k = 0, return -1.
when k = 3, return 3.

This is even tricky because we have negative numbers and an additional variable k. k can be any value, negative, don't make any assumption.

这是很复杂的，因为我们有负数，另外一个变量k可以是任何值，负的，不要做任何假设。

I cannot refer to https://en.wikipedia.org/wiki/Maximum_subarray_problem and https://www.youtube.com/watch?v=yCQN096CwWM to solve this problem.

我不能引用https://en.wikipedia.org/wiki/Maximum_subarray_problem和https://www.youtube.com/watch?要解决这个问题。

Can any body help me? Better use Java or JavaScript.

有人能帮我吗?最好使用Java或JavaScript。

Here is a classic algorithm o(n) for the maximum(no variable k):

这是一个经典的算法o(n)的最大值(没有变量k):

public int maxSubArray(int[] nums) {

        int max = nums[0];
        int tsum = nums[0];
        for(int i=1;i<nums.length;i++){
            tsum = Math.max(tsum+nums[i],nums[i]);
            max = Math.max(max,tsum);
        }

        return max;
    }

3 个解决方案

#1

This is an o(nlogn) solution referred to https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-contains-the-largest-sum-subject-to-a-constraint-that-the-sum-is-less-than-k

这是一个o(nlogn)解决方案，指的是https://www.quora.com/given-anarrayof integera -a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a- a-

private int maxSumSubArray(int[] a , int k){

    int max = Integer.MIN_VALUE;
    int sumj = 0;
    TreeSet<Integer> ts = new TreeSet();
    ts.add(0);

    for(int i=0;i<a.length;i++){
        sumj += a[i];
        Integer gap = ts.ceiling(sumj - k);
        if(gap != null) max = Math.max(max, sumj - gap);
        ts.add(sumj);
    }
}

#2

Here's a naive algorithm that runs in O(n²).

这里有一个简单的算法，在O(n)中运行。

std::array<int, 3> input = {2, 2, -1};
int k = -1;
int sum = 0, largestSum = *std::min_element(input.begin(), input.end()) -1;
int i = 0, j = 0;
int start = 0, end = 0;

while (largestSum != k && i != input.size()) {
    sum += input[j];

    if (sum <= k && sum > largestSum) {
        largestSum = sum;
        start = i;
        end = j;
    }

    ++j;
    if (j == input.size()) {
        ++i;
        j = i;
        sum = 0;
    }
}

That's C++ but it shouldn't be hard to write in Java or Javascript. It basically tries every sum possible (there are n*(n+1)/2) and stops if it finds k.

这是c++，但是用Java或Javascript编写并不难。它基本上尝试所有可能的和(有n*(n+1)/2)，如果找到k就停止。

largestSum must be initialized to a low-enough value. Since the minimum element of the input could equal k, I subtracted 1 to it.
start and end are the first and last indices of the final subarray.

必须将largestSum初始化为一个足够低的值。因为输入的最小元素可以等于k，所以我减去1。开始和结束是最后一个子数组的第一个和最后一个索引。

Of course, it could be improved if you had any constraints on the inputs.

当然，如果对输入有任何限制，可以改进。

Live example

生活的例子

#3

I was influenced by the classic solution mentioned in the question. This problem can be simply solved by an o(n^2) solution:

我受到了问题中提到的经典解决方案的影响。这个问题可以通过一个o(n 2)解决方案简单地解决:

private int maxSumSubArray(int[] a , int k){

    int max = Integer.MIN_VALUE;
    for(int i=0;i<a.length;i++){
        int tsum = 0;
        for(int j=i;j<a.length;j++){
            tsum += a[j];
            if(tsum <= k) max=Math.max(max,tsum);
        }
    }

    return max;
}

#1

private int maxSumSubArray(int[] a , int k){

    int max = Integer.MIN_VALUE;
    int sumj = 0;
    TreeSet<Integer> ts = new TreeSet();
    ts.add(0);

    for(int i=0;i<a.length;i++){
        sumj += a[i];
        Integer gap = ts.ceiling(sumj - k);
        if(gap != null) max = Math.max(max, sumj - gap);
        ts.add(sumj);
    }
}

#2