largest sum of contiguous subarray No Larger than k

Question

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.

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

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

Here is a classic algorithm o(n) for the maximum(no variable 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

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

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];
        if (sumj == k) return k;
        Integer gap = ts.ceiling(sumj - k);
        if(gap != null) max = Math.max(max, sumj - gap);
        ts.add(sumj);
    }
    return max;
}