Last Updated: 4 Mar, 2021
Maximum subsequence sum such that no three are consecutive
Moderate
Asked in companies
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
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.
Approaches
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.
The key idea is to convert the recursive approach to the dp approach by caching the solution, i.e. If we have already calculated the answer we just return the stored answer and if we haven’t calculated then we recursively solve it by the above approach.
Similar problems