largest sum of contiguous subarray No Larger than k

largest subarray having sum greater than k
maximum sum subarray having sum less than or equal to given sum
max sum of rectangle no larger than k
maximum subarray
max sum of rectangle no larger than k huahua
maximum sum subarray of size k - leetcode
maximum size subarray sum equals k
maximum sum of subarray close to k

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;
}

largest sum of contiguous subarray No Larger than k, largest sum of contiguous subarray No Larger than k find subarray with max sum less or equal than k // slight variation of "Maximum Subarray" (no less than k � // find subarray with max sum less or equal than k // slight variation of "Maximum Subarray" (no less than k requirement) which can be seen as a special case where k==Integer.MAX_VALUE so we find the max subarray sum less than +infinity which is the maximum subarray sum public int maxSubArray (int [] nums) { long k = Integer.Max_VALUE; // parameter long maxLessThanK = Integer.MIN_VALUE; TreeSet<Long> set = new TreeSet<>(); set. add (0L); // so that subarrays starting from index 0 can be

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

That's C++ but it shouldn't be hard to write in Java or Javascript. It basically tries every sum possible (there are n*(n+1)/2) and stops if it finds k.

largestSum must be initialized to a low-enough value. Since the minimum element of the input could equal 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 any constraints on the inputs.

Live example

Maximum sum subarray having sum less than or equal to given sum , Longest subarray whose elements can be made equal by maximum K increments � Subarray with difference between maximum and minimum element greater� Largest Sum Contiguous Subarray Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum. Recommended: Please solve it on “ PRACTICE ” first, before moving on to the solution.

I was influenced by the classic solution mentioned in the question. This problem can be simply solved by an o(n^2) solution:

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;
}

Largest Sum Contiguous Subarray, Maximum sum contiguous subarray within a one-dimensional array of is updated to 7 because max_ending_here is greater than max_so_far for i=7, a[7] = -3� Because the sum of rectangle [ [0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Maximum Sum of Subarray Close to K, Given an array, find the maximum sum of subarray close to k but not larger than k. Java Solution The solution to this problem is obvious when we draw. Given an array, find the maximum sum of subarray close to k but not larger than k. Java Solution. The solution to this problem is obvious when we draw the following diagram.

LeetCode – Max Sum of Rectangle No Larger Than K (Java), The key to the optimal solution is using a tree set to calculate the maximum sum of subarray close to k. Java Solution 1. public int maxSumSubmatrix(int[]� 363. Max Sum of Rectangle No Larger Than K (Hard) 364. Nested List Weight Sum II (Medium) 366. Find Leaves of Binary Tree (Medium) 368. Largest Divisible Subset (Medium) 369. Plus One Linked List (Medium) 370.

Improved algorithms for the k maximum-sums , m�n, our algorithm for finding the k maximum-sum subarrays is the first one Linear-time algorithms for finding all the non-overlapping maximal segments were given in [7,18]. We first output those elements whose values are greater than ai. Given an array A of n real numbers, the maximum subarray problem is to find a contiguous subarray which has the largest sum. The k-maximum subarrays problem is to find k such subarrays with the largest sums. For the 1-maximum subarray the well known divide-and-conquer algorithm, presented in most textbooks, although suboptimal, is easy to implement and can be made optimal with a simple change that speeds up the combine phase.

Comments
  • Any complexity requirements ?
  • No more requirement, can you solve it?
  • What value must be not greater than k? Length of subarray or sum of subarray? Answer for test [1, 2, 3], k = 2 is 5 or 2?
  • As the title, max sum of contiguous subarray no bigger than k.