You're in charge of running a scientific program (job) that simulates a physical system for as ma...

a.) let V(A,k) denote the maximum value of any plan that ends at machine A at the end of kth minute and let V(B,k) denote the maximum value of any plan that ends at machine B at the end of kth minute.

Now, if any plan ends at machine A at the end of kth sec, then at the end of k-1th second, it could be at machine A or machine B. if there is a simple shift from machine A at the end of k-1th sec to machine A itself, then a[k] is added to the max value plan and if there is a move from machine B to machine A at the end of k-1th sec, then the max value plan remains same(equal to max value plan after k-1th sec) after the kth sec as well since kth sec is utilized in moving.

Hence, we can derive the recurrence relation from this observation as below:-

V(A,k) = max( V(A,k-1) + a[k], V(B,k-1) )

similar explanation can be given for V(B,k) as well and thus the recurrence relation would be

V(B,k) = max( V(B,k-1) + b[k], V(A,k-1) )

b.) pseudo code for finding max value plan after nth sec:-

###this is a recursive code:-

max_plan(a[ ], b[ ], n){

// this is base case. if n = 1, it tells that we are at starting point and need to choose the max value from a[1] and b[1]

if( n == 1 ){

return max( a[1], b[1] )

}

// recursive calls

max_A = max( max_plan(a[ ], b[ ], n-1) + a[n], max_plan(b[ ], a[ ], n-1)

  max_B = max( max_plan(b[ ], a[ ], n-1) + b[n], max_plan(a[ ], b[ ], n-1)

// final result

return max( max_A, max_B )

}