- Maximum sum in 3-array
- 2024-03-29 10:49:29 @

**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)

# 0 comments

# Information

- ID
- 1046
- Difficulty
- 4
- Category
- DP Click to Show
- Tags
- # Submissions
- 57
- Accepted
- 25
- Accepted Ratio
- 44%
- Uploaded By