CODEWITHSUNDEEP
arraysalgorithm
rtheunissen
rtheunissen

Reputation: 7435

How to find the maximum sum of a subsequence of maximum length

I'm working on an interview question for which I couldn't find any textbook solution for. Given a list of integers, find the maximum sum of any consecutive values / sublist no longer than a given K length.

Upvotes: 1

Views: 683

Answers (4)

Niklas B.
Niklas B.

Reputation: 95348

Let p[i] be the prefix sum a[0] + ... + a[i - 1]. We can compute the sequence p easily in linear time. For a fixed index i, the maximum sum of a subarray of size at most K that has its right boundary at index i can be computed as

MAX(j = max(0, i - K + 1) to i, p[i + 1] - p[j]) = p[i + 1] - MIN(j = max(0, i - K + 1) to i, p[j])

We can process the possible right borders i in ascending order. We then want to compute for each such i the MIN term in the above formula in O(1). This is exactly the sliding window minimum problem, which has a nice solution using a special queue data structure. This queue supports the operations push/pop as well as min in amortized O(1). Using it, our algorithm looks like this:

q = new MinQueue()
sum = 0
answer = 0
for i := 0 to N - 1:
    q.push(sum)  # sum == p[i]
    if len(q) > K:
        q.pop()
    sum += a[i]
    answer = max(answer, sum - q.min())  # sum == p[i + 1]

The total runtime is linear.

Upvotes: 1

Dinesh
Dinesh

Reputation: 4559

Here is an outline. You have X[i, where i=1..N] numbers. Given K, assuming K <= N, there are N-K+1 sub-sequences, starting from 1..(N-K+1). You can store the sums in S[j, j=1..N-K+1]

Say, you already have S[j]. Then S[j+1] = S[j] - X[j-1] + X[j+K-1]. You need to find S[1], and then the rest are simple. The problem now reduces to finding the largest value in S. There can be 1 or more answers. Complexity linear.

HTH get you started.

Upvotes: 0

Tao Feng
Tao Feng

Reputation: 1

The N numbers are X[0],...X[N-1] and assuming 1<=K<=N. S[i,l] stands for the maximum sum of the sublist that starts from i and has no more than l length.

You have S[i,1] = X[i] and then S[i,l] = MAX(S[i+1, l-1]+X[i], X[i]), where l>=2.

The final answer is MAX(S[i,K], where i<=N-1 and i>=0).

Upvotes: 0

Sunil Sistla
Sunil Sistla

Reputation: 66

It looks similar to maximum subarray problem. refer _http://en.wikipedia.org/wiki/Maximum_subarray_problem_ 

var arr = [1,2,31,24,34,3,23,24,3,25,34,54,3,2,34];
var getSmallestSubSeqSum = function(arr, k){
    var totalLength = arr.length, index = 0, sums= [];
    for(index=0;index < totalLength-k+1;index++)
    {
        sums.push(0);
    }

    for(var index=0; index < totalLength-k+1;index++)
    {
        for(var aI = 0; aI < k; aI++)
        {
            sums[index] += arr[index + aI];
        }
    }
    console.log('Total Length: ' + totalLength);
    console.log('Sub Length: ' + 3);    
    console.log('sums length: ' + sums.length);
    console.log("Array: "+arr);

    index = Math.max.apply(Math, sums);
    console.log('Max Sum: ' + index);
    console.log("Sums: "+ sums);

    index = sums.indexOf(index);
    console.log("max sum sub array: " + arr.slice(index, index + k));
};

getSmallestSubSeqSum(arr, 6);

The above code snippet should help this is javascript.

Upvotes: 0

Related Questions