CODEWITHSUNDEEP
dynamic-programmingsub-arraysubsequence
rockmyboat
rockmyboat

Reputation: 187

Maximum sum of contiguous sub-sequence with length at most k

I am trying to modify the Kadane Algorithm in order to solve a more specific problem. 

def max_Sum(arr, length, k):
if length < k:
    print('length of array should be greater than k')

res = 0
for i in range(0, k):
    res += arr[i]

current_sum = res

for i in range(k, n):
    if k == n:
        for j in range(0, k-1):
            res += arr[j]
        current_sum = res
    else:
        current_sum += arr[i] - arr[i-k]
        print(res, current_sum)
        res = max(res, current_sum)

return res

This is the code for the maximum subarray problem. What I want to do is find the maximum subarray with length at most K.

Example: We have an array A = [3,-5 1 2,-1 4,-3 1,-2] and we want to find the maximum subarray of length at most K = 9. Length of subarray should not be restricted at K, if there is another length L < K that provides a greater sum, the algorithm should return sum[:L].

In this case, the algorithm will return 0. It should return 6, following the sum of A[2:5].

Upvotes: 5

Views: 6491

Answers (5)

גלעד ברקן
גלעד ברקן

Reputation: 23955

There is an O(n) solution at https://cs.stackexchange.com/a/151327/10147

We can solve this with O(n log n) complexity by divide and conquer. Consider the left and right halves of the array: the solution is either in (1) the left half exclusively, (2) the right half exclusively, or (3) a suffix of the left combined with a prefix of the right.

To solve (3) in O(n), iterate from the middle to the left, recording for each index the higher of the highest seen or the total sum. Then iterate to the right and add a similar record for prefix length l with the recorded value for index k - l (or the longest possible if k-l is out of bounds) in the first iteration.

For the example, [3,-5, 1, 2,-1, 4,-3, 1,-2] k = 9, we have:

[3,-5, 1, 2,-1, 4,-3, 1,-2]
 2  2  2  1  0  <---
          --->  4  4  4  4
 ^-----------------------^
     best = 2 + 4 = 10

Upvotes: 0

user22379956
user22379956

Reputation: 9

O(n) solution

long getMaxProfit(vector<int> pnl, int k) {
    int n = pnl.size();
    long maxprofit = 0;
    int i;
    long profit = 0;
    int start = 0;
    for(i=0;i<n;i++) {
        profit += pnl[i];
        if (profit <= 0) {
            profit = 0;
            start = i+1;
        } else {
            maxprofit = max(maxprofit , profit);
            //slide window if it's size is k
            if (i-start+1 == k) {
                //pnl[start] can never be negative because if it is 
                //negative it would have been removed in previous 
                //minimization
                profit -= pnl[start];
                start++;
            }
             //minimize window if it's size is k
            while(pnl[start] <= 0 && start <=i) {
                profit -= pnl[start];
                maxprofit = max(maxprofit , profit);
                start++;
            }
        }
    }
    return maxprofit;
}

Upvotes: 1

Sarfaraz Sheikh
Sarfaraz Sheikh

Reputation: 1

Solution in java with time complexity : O(n*k)

public static int maxSumforFixedSizeK(int[] arr, int k){

    // Using simple window sliding technique
    int best_sum;
    int curr_sum=0;

    for( int i=0;i<k;i++)
        curr_sum += arr[i];

    best_sum = curr_sum;

    for( int i=k; i<arr.length; i++) {
        curr_sum += (arr[i] - arr[i - k]);
        best_sum = Math.max(best_sum, curr_sum);
    }

    return best_sum;
}

public static int maxSumforSizeAtMostK(int[] arr, int k){
    int best_sum = Integer.MIN_VALUE;

    // Calculate maximum sum for every window size in interval [1,k] 
    for( int i=1; i<=k; i++ )
        best_sum = Math.max( best_sum, maxSumforFixedSizeK(arr, i) );

    return best_sum;
}

Upvotes: 0

skyfiretime
skyfiretime

Reputation: 85

For those who are seeking an answer in O(n), you can easily adapt the answer to this question over at CS StackExchange. The answer solves the same problem in O(n) where subsequence's length must be in a given range. For this problem, just set the range to [0, k].

Upvotes: 2

Francisco Geiman
Francisco Geiman

Reputation: 400

Well, a solution that works in O(n * K) is to use sliding windows for every possible length <= K. I have tried to find a O(n) correct solution modifying Kadane, but I couldn't.

def best_array_fixed_k( arr, length, k ):
    total_sum = 0
    best = 0
    for x in xrange( 0, length ):
        total_sum = total_sum + arr[x]
        if x >= k:
            total_sum = total_sum - arr[x - k]
        if x >= k - 1:
            best = max( best, total_sum )
            # this makes sure that we are considering a window with length = k
    return best

def max_sum( arr, length, k):
    best = 0
    for x in xrange( 1, k + 1):
        best = max( best, best_array_for_fixed_k(arr, length, x ) )
    return best

Upvotes: 1

Related Questions