连续子阵列的最大总和不大于k

Question

例如,我们有

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

这甚至是棘手的,因为我们有负数和一个额外的变量k.k可以是任何值,负数,不做任何假设.

我不能参考https://en.wikipedia.org/wiki/Maximum_subarray_problem和https://www.youtube.com/watch?v=yCQN096CwWM来解决这个问题.

有谁能够帮我？更好地使用Java或JavaScript.

这是最大的经典算法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;
    }

Answer 1

这是一个o(nlogn)解决方案,参考 https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-c​​ontains-在大森学科对一个约束,即最总和,是-低于-K

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