Maximize total tips

A restaurant received n orders. The two waiters A and B in the restaurant change different amount of tip, listed in A[] and B[], for an order. Given A can handle max X order and B can handle max Y order, Find out the maximum possible amount of total tips to handle all the orders.

Hint

Start from the end of the order list. Decide which waiter ('a' or 'b') is the better choice for the last order.

• If you choose waiter 'a' for the last order: Return a's tip for the order plut calculation of max tips for the remaining orders after reduce the number of available orders from 'a' by 1.
• If you choose waiter 'b' for the last order: Return b's tip for the order plut calculation of max tips for the remaining orders after teduce the number of available orders from 'b' by 1.

Continue this process until either all orders from 'a' or all orders from 'b' are fulfilled. Once one waiter runs out of orders, the remaining orders must be fulfilled by the other waiter.

• Python
• Javascript
•  Run

def count(a, b, x, y, n):
  if n == 0:
    return 0

  if x > 0 and y > 0:
    return max(a[n-1] + count(a, b, x-1, y, n-1), b[n-1] + count(a, b, x, y-1, n-1))

  return b[n-1] + count(a, b, x, y-1, n-1) if (x == 0) else a[n-1] + count(a, b, x-1, y, n-1)

N = 5
A = [1, 2, 3, 4, 5]
B = [5, 4, 3, 2, 1]
X = 3
Y = 3

print(count(A, B, X, Y, N))

function count(a, b, x, y, n) {
  if (n == 0) {
    return 0;
  }

  if (x > 0 && y > 0) {
    return Math.max(a[n-1] + count(a, b, x-1, y, n-1), b[n-1] + count(a, b, x, y-1, n-1));
  }

  return (x == 0) ? b[n-1] + count(a, b, x, y-1, n-1) : a[n-1] + count(a, b, x-1, y, n-1);
}

const N = 5;
const A = [1, 2, 3, 4, 5];
const B = [5, 4, 3, 2, 1];
const X = 3;
const Y = 3;

console.log(count(A, B, X, Y, N));