CODEWITHSUNDEEP
algorithmrecursion
Samer Tufail
Samer Tufail

Reputation: 1894

Recursive Maximum Subsequence Sum With No Three Consective Elements

I am attempting to solve, using recursion a way to maximize sub sequence sum such that no three elements are consecutive.

There is a way to do this by dynamic programming but I want to build on it using recursion first.

Some sample input and outputs:

Input:{1, 2, 3}
Output: 5

Input:{100, 1000, 100, 1000, 1}
Output: 2101

Input:{1, 2, 3, 4, 5, 6, 7, 8}
Output: 27

I am able to get mostly correct results apart from the second one {100, 1000, 100, 1000, 1}.

My solution:

int maxSubsequenceSum(vector<int> nums)
{
    return helper(nums, nums.size());
}

int helper(vector<int>& nums, int index)
{
    if (index <= 0) return 0;

    int withoutThird = helper(nums, index - 3) + nums[index - 1] + nums[index - 2];
    int withoutSecond = helper(nums, index - 3) + (index - 1 < 0 ? 0 : nums[index - 1]) + (index - 3 < 0 ? 0 : nums[index - 3]);
    int withoutFirst = helper(nums, index - 3) + (index - 2 < 0 ? 0 : nums[index - 2]) + (index - 3 < 0 ? 0 : nums[index - 3]);
    return max(withoutThird, max(withoutSecond, withoutFirst));
}

Individually the three withoutThird, withoutSecond and withoutFirst give the correct result only whilst in a recursive arrangement it fails. Why does it fail and is this a correct recursive approach?

Upvotes: 0

Views: 568

Answers (2)

delta
delta

Reputation: 3818

Problem

withoutSecond and withoutFirst has some bugs. To make it simpler, let's assume index >= 3. Look at withoutSecond:

withoutSecond = helper(nums, index - 3) + nums[index - 1] + nums[index - 3]

It picks index-1 and index-3. So if we pick index-4 in helper(nums, index - 3) then we can not pick index-5, but it contains in withoutThird in function helper(nums, index - 3). That would yield a larger result than expected.

Algorithm

As the condition is does not allow 3 consecutive elements. So we only need to consider 2 consecutive elements to decide if we should pick another or not.

Suppose f(a, n) calculates largest result of array a with size n.

  1. If does not pick a[n]: f(a, n) -> f(a, n-1)
  2. If pick a[n] && pick a[n-1]: f(a, n) -> f(a, n-3) + a[n] + a[n-1]
  3. If pick a[n] && not pick a[n-1]: f(a, n) -> f(a, n-2) + a[n]

OK, that's all the 3 cases.

Code

See the following code for details

#include <vector>
#include <cstdio>
using namespace std;

// this runs slow
// but you can use memorized search to speed up the process
int helper(vector<int>& nums, int index) {
    if (index == 0) return 0;
    if (index == 1) return nums[0];
    if (index == 2) return nums[0] + nums[1];

    int without_last_1                 = helper(nums, index-1);
    int with_last_1_and_2              = helper(nums, index-3) + nums[index-1] + nums[index-2];
    int with_last_1_and_without_last_2 = helper(nums, index-2) + nums[index-1];

    return max(without_last_1, max(with_last_1_and_2, with_last_1_and_without_last_2));
}

int maxSubsequenceSum(vector<int> nums) {
    return helper(nums, nums.size());
}

int main() {
    printf("%d\n", maxSubsequenceSum({1, 2, 3}));
    printf("%d\n", maxSubsequenceSum({100, 1000, 100, 1000, 1}));
    printf("%d\n", maxSubsequenceSum({1, 2, 3, 4, 5, 6, 7, 8}));
    return 0;
}

Upvotes: 1

Karan Arora
Karan Arora

Reputation: 122


The problem is to get maximum with no three consecutive elements.

What you are doing is, taking 3 elements at a time, select two having maximum sum from it, add them and so on.

Taking one example :-

Input : {A, B, C, D, E, F}

As your recursion goes right to left.
Assume, taking, {D, E, F}
(D + E) > (E + F) and (D + E) > (D + F)
Your code will select {D, E} from last 3 elements.

Now, taking, {A, B, C}
Assuming, (B + C) > (A + B) and (B + C) > (A + C)
Your code will select {B, C} from first 3 elements.

Total Selected Elements = {B, C, D, E}.
Noticed Something?
You ended up adding four continuous elements.

One short example : {100, 1000, 100, 1000, 1}
2 windows : [0,1] and [2,4]
Selected {100, 1000} from [2, 4]
and Selected {100, 1000} from [0, 1]
Added up four continuos elements.
Got: 2200, which is your actual output.

Hint: Try to pass the element index which u didn't add from one state of recursion to another. If still stuck, comment and I will write a similar code :)

Upvotes: 2

Related Questions