Maximum subsequence sum such that no three are consecutive

Difficulty Level Medium
Frequently asked in 24*7 Innovation Labs Accenture Amazon Delhivery PayPal PayU
Array Dynamic ProgrammingViews 2239

The problem “Maximum subsequence sum such that no three are consecutive ” states that you are given an array of integers. Now you need to find a subsequence that has the maximum sum given that you cannot consider three consecutive elements. To recall, a subsequence is nothing but an array that is left when some of the elements are removed from the original input array keeping the order same.

Example

Maximum subsequence sum such that no three are consecutive

a[] = {2, 5, 10}

50

Explanation

This was an easy choice to pick 5 and 10. Because any other way will not result in a larger sum.

a[] = {5, 10, 5, 10, 15}
40

Explanation

We don’t pick the 5 that is in the middle of the array. Because that will create a subsequence that does not satisfy the condition imposed in the question.

Approach

The problem has asked us to find the subsequence with a maximum sum such that no three consecutive elements are picked. Thus a naive approach could be the generation of the subsequences. As we have done in some of the previous questions. The naive approach is most of the time, to generate the subsequences then check whether the subsequence satisfies the conditions which are imposed in the question. But this approach is time-consuming and can not be used practically. Because using the approach for even moderate-sized inputs will exceed the time limits. Thus to solve the problem we need to use some other method.

We will use Dynamic Programming to solve the problem but before that, we need to perform some casework. This casework is done to reduce the initial problem into smaller subproblems. Because in Dynamic Programming, we reduce the problem into smaller subproblems. So, consider we skip the current element then our problem is reduced to solving the problem until the previous element. Consider, we do pick the current element. Then we have two choices for the previous element. Either we pick the previous element, if we do then we cannot choose the element the previous to previous element. But if we don’t, the problem is reduced to solving the problem until the previous to the previous element. It will be easier to understand using the code.

Code

C++ code to find maximum subsequence sum such that no three are consecutive

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
    int dp[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = max({a[0] + a[1], a[2]+a[0], a[2]+a[1]});
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = max({a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i], dp[i-1]});
    cout<<dp[n-1];
}

16

Java code to find maximum subsequence sum such that no three are consecutive

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = a.length;
    int dp[] = new int[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = Math.max(Math.max(a[0] + a[1], a[2]+a[0]), a[2]+a[1]);
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = Math.max(Math.max(a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i]), dp[i-1]);

    System.out.println(dp[n-1]);
  }
}
16

Complexity Analysis

Time Complexity

O(N), because we had simply traversed the array and kept on filling our DP array. Thus the time complexity is linear.

Space Complexity

O(N), because we had to make a one dimensional DP array to store the values. The space complexity is also linear.

Translate »