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;
}
Simple Approach: Run a loop for i from 0 to n – 1, where n is the size of the array. Now, we will run a nested loop for j from i to n – 1 and add the value of the element at index j to a variable currentMax. Lastly, for every subarray, we will check if the currentMax is the maximum sum of all contiguous subarrays.
It can be a single element of an array or some fraction of the array. The largest sum contiguous subarray means a subarray that has the maximum sum value. For example, an array is {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Its sub arrays can be: {-10,5,1,6} or {5,1,6} or {2,7,3, -5} etc.
Naive Approach: We can find the maximum sum of the subarray by running two loops. But the time complexity will be O(N*N). Efficient Approach: The subarray having maximum sum can be found by using a sliding window. If curr_sum is less than sum include array elements to it.
Don't be afraid this is not very difficult.... For new programmer, this is very essential... We know a little bit for that we don't answer many problem as like "largest sum contiguous sub array" that's really very easy to determine largest sum if we know the following algorithm.....
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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With