3

I have this problem , where given an array of positive numbers i have to find the maximum sum of elements such that no two adjacent elements are picked. The maximum has to be less than a certain given K. I tried thinking on the lines of the similar problem without the k , but i have failed so far.I have the following dp-ish soln for the latter problem

    int sum1,sum2 = 0;
    int sum = sum1 = a[0];

    for(int i=1; i<n; i++)
    {
        sum = max(sum2 + a[i], sum1);
        sum2 = sum1;
        sum1 = sum;
    }

Could someone give me tips on how to proceed with my present problem??

Improve this question
2
  • Max sum of 2 elements such that no two adjacent elements are picked? 2 or more? Commented Apr 21, 2012 at 18:13
  • Max sum obtained over all the elements in the array without picking adjacent elements... Commented Apr 21, 2012 at 20:15

4 Answers 4

Reset to default
4

The best I can think of off the top of my head is an O(n*K) dp:

int sums[n][K+1] = {{0}};
int i, j;
for(j = a[0]; j <= K; ++j) {
    sums[0][j] = a[0];
}
if (a[1] > a[0]) {
    for(j = a[0]; j < a[1]; ++j) {
        sums[1][j] = a[0];
    }
    for(j = a[1]; j <= K; ++j) {
        sums[1][j] = a[1];
    }
} else {
    for(j = a[1]; j < a[0]; ++j) {
        sums[1][j] = a[1];
    }
    for(j = a[0]; j <= K; ++j) {
        sums[1][j] = a[0];
    }
}
for(i = 2; i < n; ++i) {
    for(j = 0; j <= K && j < a[i]; ++j) {
        sums[i][j] = max(sums[i-1][j],sums[i-2][j]);
    }
    for(j = a[i]; j <= K; ++j) {
        sums[i][j] = max(sums[i-1][j],a[i] + sums[i-2][j-a[i]]);
    }
}

sums[i][j] contains the maximal sum of non-adjacent elements of a[0..i] not exceeding j. The solution is then sums[n-1][K] at the end.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

+1: Also, correct me if I am wrong - but I believe there is a reduction from subset-sum problem: given an instance of subset-sum, "pad" the elements: between every 2 adjacent elements - add a value k+1. Thus, a polynomial solution is not likely to be found, and the proposed pseudo-polynomial solution is probably optimal. [unless k < 2^n of course, and then just check all combinations...]
0
  1. Make a copy (A2) of the original array (A1).
  2. Find largest value in array (A2).
  3. Extract all values before the it's preceeding neighbour and the values after it's next neighbour into a new array (A3).
  4. Find largest value in the new array (A3).
  5. Check if sum is larger that k. If sum passes the check you are done.
  6. If not you will need to go back to the copied array (A2), remove the second larges value (found in step 3) and start over with step 3.
  7. Once there are no combinations of numbers that can be used with the largest number (i.e. number found in step 1 + any other number in array is larger than k) you remove it from the original array (A1) and start over with step 0.
  8. If for some reason there are no valid combinations (e.g. array is only three numbers or no combination of numbers are lower than k) then throw an exception or you return null if that seems more appropriate.
Improve this answer

3 Comments

You are not done in step 5 you have to get as close to K as possible. Example 2 6 2 k=5 your solution would be 0 correct solution is 4
I do not follow your logic. If I check that the sum of two of the largest numbers in the array is lower than K and I have ensured they are not adjacent one another then I would be done. In the case of 2 6 2 and k=5 it would go like this: 6 is highest, but there are no values in the new array (adjacent numbers are not included in new array) so go we end up in step 7. Largest number is 2 (step2). (step3) In the new array (A3) there will only be a 2 (step 4). (step5) 2+2 is less than 5 so return sum.
@JensSchauder I made the assumption that the question was about finding the two sum of the two largest non adjacent numbers.
0

First idea: Brute force

Iterate all legal combination of indexes and build the sum on the fly.

Stop with one sequence when you get over K.

keep the sequence until you find a larger one, that is still smaller then K

Second idea: maybe one can force this into a divide and conquer thing ...

Improve this answer

Comments

0

Here is a solution to the problem without the "k" constraint which you set out to do as the first step: https://stackoverflow.com/a/13022021/1110808

The above solution can in my view be easily extended to have the k constraint by simply amending the if condition in the following for loop to include the constraint: possibleMax < k

// Subproblem solutions, DP
for (int i = start; i <= end; i++) {
    int possibleMaxSub1 = maxSum(a, i + 2, end);
    int possibleMaxSub2 = maxSum(a, start, i - 2);

    int possibleMax = possibleMaxSub1 + possibleMaxSub2 + a[i];
    /*
    if (possibleMax > maxSum) {
        maxSum = possibleMax;
    }
    */
    if (possibleMax > maxSum && possibleMax < k) {
        maxSum = possibleMax;
    }
}

As posted in the original link, this approach can be improved by adding memorization so that solutions to repeating sub problems are not recomputed. Or can be improved by using a bottom up dynamic programming approach (current approach is a recursive top down approach)

You can refer to a bottom up approach here: https://stackoverflow.com/a/4487594/1110808

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.