text: Maximum sum from three arrays such that picking elements consecutively from same is not allowed | C ++ implementation of the approach ; Function to return the maximum sum ; Base case ; Already visited ; If the element has been taken from first array in previous step ; If the element has been taken from second array in previous step ; If the element has been taken from third array in previous step ; Driver code ; Pick element from first array ; Pick element from second array ; Pick element from third array ; Print the maximum of them
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 3 ; int FindMaximumSum ( int ind , int kon , int a [ ] , int b [ ] , int c [ ] , int n , int dp [ ] [ N ] ) { if ( ind == n ) return 0 ; if ( dp [ ind ] [ kon ] != -1 ) return dp [ ind ] [ kon ] ; int ans = -1e9 + 5 ; if ( kon == 0 ) { ans = max ( ans , b [ ind ] + FindMaximumSum ( ind + 1 , 1 , a , b , c , n , dp ) ) ; ans = max ( ans , c [ ind ] + FindMaximumSum ( ind + 1 , 2 , a , b , c , n , dp ) ) ; } else if ( kon == 1 ) { ans = max ( ans , a [ ind ] + FindMaximumSum ( ind + 1 , 0 , a , b , c , n , dp ) ) ; ans = max ( ans , c [ ind ] + FindMaximumSum ( ind + 1 , 2 , a , b , c , n , dp ) ) ; } else if ( kon == 2 ) { ans = max ( ans , a [ ind ] + FindMaximumSum ( ind + 1 , 1 , a , b , c , n , dp ) ) ; ans = max ( ans , b [ ind ] + FindMaximumSum ( ind + 1 , 0 , a , b , c , n , dp ) ) ; } return dp [ ind ] [ kon ] = ans ; } int main ( ) { int a [ ] = { 6 , 8 , 2 , 7 , 4 , 2 , 7 } ; int b [ ] = { 7 , 8 , 5 , 8 , 6 , 3 , 5 } ; int c [ ] = { 8 , 3 , 2 , 6 , 8 , 4 , 1 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int dp [ n ] [ N ] ; memset ( dp , -1 , sizeof dp ) ; int x = FindMaximumSum ( 0 , 0 , a , b , c , n , dp ) ; int y = FindMaximumSum ( 0 , 1 , a , b , c , n , dp ) ; int z = FindMaximumSum ( 0 , 2 , a , b , c , n , dp ) ; cout << max ( x , max ( y , z ) ) ; return 0 ; }