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;
}
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];
Integer gap = ts.ceiling(sumj - k);
if(gap != null) max = Math.max(max, sumj - gap);
ts.add(sumj);
}
return max;
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments