CODEWITHSUNDEEP
algorithmqueuedynamic-programmingbinary-searchkadanes-algorithm
Jerry Z.
Jerry Z.

Reputation: 2051

largest sum of contiguous subarray No Larger than 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;
    }

Upvotes: 13

Views: 14436

Answers (7)

Aashutosh Gupta
Aashutosh Gupta

Reputation: 9

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

Upvotes: -1

Jerry Z.
Jerry Z.

Reputation: 2051

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

Upvotes: 14

akshay kumar
akshay kumar

Reputation: 1

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;

Upvotes: 0

pulkit
pulkit

Reputation: 1

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

Upvotes: 0

maindoor
maindoor

Reputation: 67

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

Upvotes: 0

Jerry Z.
Jerry Z.

Reputation: 2051

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

Upvotes: 1

Nelfeal
Nelfeal

Reputation: 13269

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

Upvotes: 0

Related Questions