Maximum Prefix Sum possible by merging two given arrays | C # implementation of above approach ; Stores the dp states ; Recursive Function to calculate the maximum prefix sum ontained by merging two arrays ; If subproblem is already computed ; If x >= N or y >= M ; If x < N ; If y < M ; Otherwise ; Driver code
using System ; using System . Collections . Generic ; class GFG { static Dictionary < Tuple < int , int > , int > dp = new Dictionary < Tuple < int , int > , int > ( ) ; static int maxPreSum ( int [ ] a , int [ ] b , int x , int y ) { if ( dp . ContainsKey ( new Tuple < int , int > ( x , y ) ) ) return dp [ new Tuple < int , int > ( x , y ) ] ; if ( x == a . Length && y == b . Length ) return 0 ; int curr = 0 ; if ( dp . ContainsKey ( new Tuple < int , int > ( x , y ) ) ) { curr = dp [ new Tuple < int , int > ( x , y ) ] ; } if ( x == a . Length ) { curr = Math . Max ( curr , b [ y ] + maxPreSum ( a , b , x , y + 1 ) ) ; } else if ( y == b . Length ) { curr = Math . Max ( curr , a [ x ] + maxPreSum ( a , b , x + 1 , y ) ) ; } else { int max = Math . Max ( a [ x ] + maxPreSum ( a , b , x + 1 , y ) , b [ y ] + maxPreSum ( a , b , x , y + 1 ) ) ; curr = Math . Max ( curr , max ) ; } dp [ new Tuple < int , int > ( x , y ) ] = curr ; return dp [ new Tuple < int , int > ( x , y ) ] ; } static void Main ( ) { int [ ] A = { 2 , 1 , 13 , 5 , 14 } ; int [ ] B = { - 1 , 4 , - 13 } ; Console . WriteLine ( maxPreSum ( A , B , 0 , 0 ) ) ; } }