Prerequisite : Dynamic Programming
Problem statement summary :
You are given 3 array A[], B[], C[] of equal length N.
You need to construct an Array D[] in following way,
Array D[] has exaclty N elements.
All selective elements comes from A[], B[] or C[].
You can select only Ai,Bi,Ci-th element for all i from 1 to N.,in other words if you select the 2nd element from array A[] then you cannot take the 2nd elements of array B[] and C[] and vice versa.
you cannot select same index twice from any array and two consecutive elements from any array.
Total sum of array D[] is as maximum as possible.
Solution :
If you select ith Position for any array then transition should be,
Ai = max( Bi-1 , Ci-1)
Bi = max( Ai-1 , Ci-1),
C i= max(Ai-1 , Bi-1),
More formally, Dp[N][3] = Dp[position] [array no. ]
Let’s see, 1 = A[], 2=B[], 3 = C[]
1 <= i <= N,
Dp[i][1] = max( Dp[i-1][2] , Dp[i-1][3] ) + A[i];
Dp[i] [2] = max( Dp[i-1] [1] , Dp[i-1] [3] ) + B[i];
Dp[i] [3] = max( Dp[i-1] [1] , Dp[i-1] [2] ) + C[i].
Answer is always , max (Dp[n][1] , Dp[n][2], Dp[n][3]).
Time Complexity : O(N)