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

Militarism

Any complexity requirements ? – Xylia

No more requirement, can you solve it? – Militarism

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? – Brock

As the title, max sum of contiguous subarray no bigger than k. – Militarism

Candidate for migration to: codegolf.stackexchange.com – Soy

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

Militarism

Answer 2

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

Militarism

Answer 3

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

Xylia

Answer 4

Here's one in python O(n^2):

def maxsubfunc(arr, k):
  s = 0
  maxsofar = -1
  for i,n in enumerate(arr):
    s += n
    if s <= k:
        maxsofar = max(maxsofar, s)
    else:
        maxnow = s
        for j in range(i):
            maxnow -= arr[j]
            if maxnow < k:
                maxsofar = max(maxnow, maxsofar)
 return maxsofar

Watercolor

Answer 5

Wonder why no one's discussing the Sliding Window based Solution for this( O(n) ).

1. Initialise the window with first element. Keep track of start index of window.
2. Iterate over the array, adding the current element to window.
3. If sum becomes > k, reduce the window from start until sum becomes <= k.
4. Check if sum > maxSumSoFar, set maxSumSoFar = sum.

Note -> 'sum' in above algo is the sum of elements in current window.

int findMaxSubarraySum(long long arr[], int N, long long K)
{
    long long currSum = arr[0];
    long long maxSum = LLONG_MIN;
    int startIndex = 0;
    if(currSum <= X) maxSum = currSum;
    for(int i=1; i<N; i++){
        currSum += arr[i];
        while(currSum > K && startIndex <= i){
            currSum -= arr[startIndex];
            startIndex++;
        }
        if(currSum <= K) maxSum = max(maxSum, currSum);
    }
    return (int)maxSum;
} 

Frey

Does this work even if there are negative numbers? – Rothmuller

Answer 6

Can be solved using simple sliding window. First keep adding sum of array elements and if sum exceeds k decrease it by subtracting elements from start. This works only if array has non-negative numbers.

int curr_sum = arr[0], max_sum = 0, start = 0;

// To find max_sum less than sum
for (int i = 1; i < n; i++) {

    // Update max_sum if it becomes
    // greater than curr_sum
    if (curr_sum <= sum)
       max_sum = max(max_sum, curr_sum);

    // If curr_sum becomes greater than
    // sum subtract starting elements of array
    while (curr_sum + arr[i] > sum && start < i) {
        curr_sum -= arr[start];
        start++;
    }
     
    // Add elements to curr_sum
    curr_sum += arr[i];
}

// Adding an extra check for last subarray
if (curr_sum <= sum)
    max_sum = max(max_sum, curr_sum);

return max_sum;

Rubbing

Answer 7

# 3 steps to solve Kadane's Algorithm
//approach
sum=0
maxi=arr[0]
for i=0 to arr.length {
//steps
1. sum=sum+arr[i]
2. maxi=max(maxi,sum)
3. if(sum<0) -> sum=0
}
return maxi

//solution

nums=[-2,1,-3,4,-1,2,1,-5,4]

class Solution {
public int maxSubArray(int[] nums) {
    int sum=0; 
    int maxi=nums[0]; 
    for(int i=0 ; i<nums.length ; i++){ 
        sum+=nums[i]; 
        maxi=Math.max(maxi,sum); 
        if(sum<0){ 
            sum=0; 
        } 
    } 
    return maxi; 
    
} 





  

Bedwarmer

Can you give a little more context? Why this solution works, and what the performance is, would be helpful. – Soy

you can refer LeetCode solution leetcode.com/submissions/detail/887255042 – Bedwarmer