Maximum subsequence sum such that no three are consecutive

Moderate
0/80
Average time to solve is 15m
20 upvotes
Asked in companies
AmazonSamsungDunzo

Problem statement

You are given an array A of length N consisting of positive integers. Your task is to print the maximum subsequence sum such that no three consecutive elements are taken from array A.

Note:

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’, representing the length of the array.

The second line of each test case contains 'N' space-separated integers of the array 'A'.
Output Format: 
For each test case, print a single line containing a single integer denoting the maximum sum subsequence.

The output of each test case will be printed on a new line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10 ^ 4
1 <= A[i] <=10 ^ 5

Where ‘T’ denotes the number of test cases and N denotes the length of array 'A'.

Time limit: 1 sec.
Sample Input 1:
2
3
1 1 1 
4
6 3 3 2
Sample Output 1:
2
11
Explanation for Sample Input 1:
For test case 1: 

All subsequences sum  are:  
1 (A[0]), 1 (A[1]), 1 (A[2]), 2 (A[0] + A[1]), 2 (A[0] + A[2]), 2 (A[1] + A[2]), 3(A[0] + A[1] + A[2]) 

The max sum subsequence without three consecutive elements is 2 ( A[0] + A[1] or A[0] + a[2] or A[1] + A[2]).

For test case 2:

All subsequences sum are:  
6 (A[0]), 3 (A[1]), 3 (A[2]), 2 (A[3]),  9 (A[0] + A[1]), 9 (A[0] + A[2]), 8 (A[0] + A[3]), 6 (A[1] + A[2]), 5 (A[1] + A[3]), 5 *  (A[2] + A[3]), … 11 (A[0] + A[1] + A[3]), ... 11 (A[0] + A[2] + A[3])

The max sum subsequence without three consecutive elements is 11 ( A[0] + A[1] + A[3]  or A[0] + A[2] + A[3] ).
Sample Input 2:
2
8
1 2 3 4 5 6 7 8
1
46
Sample Output 2:
27
46
Hint

Think of exploring all possible combinations under the given conditions.

Approaches (2)
Recursion

Explanation:

 

The key idea is to build our current answer from previous answers, i.e. if we want to calculate the answer from the first ‘i’ elements (0...i), we can use answers from the prefix of i-1, i-2, i-3 elements.

solve(A,i) = max( solve(A,i-1), A[i] + solve(A,i-2), A[i]+A[i-1] +solve(A,i-3) );

 

To calculate the maximum subsequence sum of the first i elements we have 3 parts:

  • solve(A,i)= solve(A, i - 1), i.e. we are not taking the element in the current index.
  • solve(A,i)= A[i] + solve(A, i - 2), i.e. we are taking the current indexed value but we aren’t taking the value at index i-1, and thus using solve(A, i - 2) to find the max sum in first i-2 elements.
  • solve(A,i)= A[i] + A[i - 1] + solve(A, i - 3), i.e. we will taking current and prev value, and use solve(A, i - 3) to find the max sum in first i - 3 elements.

To make sure we do not use 3 consecutive elements from the array, we deliberately skip some elements.

 

Algorithm:

  • If  i<= 2 ( i.e.  i = {0, 1, 2}) manually solve the problem.
  • Solve the problem recursively using the above recursive formula.
  • Return solve(A, N - 1),  which is the answer.
Time Complexity

O(3 ^ N),  where ‘N’ is the length of the array.

 

As from every position in the array, we are calling 3 more functions in previous positions.

Space Complexity

O(N), where ‘N’ is the length of the array.

 

The depth of the recursion tree will be O(N), thus space O(N) is space occupied by the stack.

Code Solution
(100% EXP penalty)
Maximum subsequence sum such that no three are consecutive
Full screen
Console