Largest sum of adjacent subarray None greater than k

Question

For example, we have

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

This is even difficult because we have negative numbers and an additional variable k. k can be any value negative, make no assumptions.

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

Can anyone help me out? Better use Java or JavaScript.

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

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

Answer 2

Here's a naive algorithm that works in 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; } } 

This is C ++, but it should not be difficult to write in Java or Javascript. He basically tries every possible sum (there is n*(n+1)/2 ) and stops if he finds k.

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

Of course, it could be improved if you had restrictions on the input data.

Living example

Answer 3

I was influenced by the classic solution mentioned in the question. This problem can simply be solved using the 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; }