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.

Table of Contents

## Example

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.