Maximum Tip Calculator Java

PROGRAM TO CALCULATE THE MAXIMUM TIP

import java.io.*;

import java.util.HashMap;

 

class GFG {

 

    // Function that finds the maximum tips

    // from the given arrays as per the

    // given conditions

    static int maximumTip(int[] arr1, int[] arr2, int n,

                          int x, int y,

                          HashMap<String, Integer> dd)

    {

        // Create key of N, X, Y

        String key = Integer.toString(n) + "_"

                     + Integer.toString(x) + "_"

                     + Integer.toString(y);

       

        // Return if the current state is

        // already calculated

        if (dd.get(key) != null)

            return dd.get(key);

        // Base Condition

        if (n == 0)

            return 0;

 

        // If both have non-zero count then store and

        // return max element from both array

        if (x != 0 && y != 0) {

            int temp = Math.max(

                arr1[n - 1]

                    + maximumTip(arr1, arr2, n - 1, x - 1,

                                 y, dd),

                arr2[n - 1]

                    + maximumTip(arr1, arr2, n - 1, x,

                                 y - 1, dd));

            dd.put(key, temp);

            // Return the current state result

            return dd.get(key);

        }

 

        // if y is zero, only x value

        // can be used

        if (y == 0) {

            int temp = arr1[n - 1]

                       + maximumTip(arr1, arr2, n - 1,

                                    x - 1, y, dd);

            dd.put(key, temp);

            // Return the current state result

            return dd.get(key);

        }

 

        // if x is zero, only y value

        // can be used

        else {

            int temp = arr2[n - 1]

                       + maximumTip(arr1, arr2, n - 1, x,

                                    y - 1, dd);

            dd.put(key, temp);

            // Return the current state result

            return dd.get(key);

        }

    }

 

    // Driver Code

    public static void main(String[] args)

    {

        int N = 5;

        int X = 3;

        int Y = 3;

 

        int A[] = { 1, 2, 3, 4, 5 };

        int B[] = { 5, 4, 3, 2, 1 };

       

        // Stores the results of the

        // overlapping state

        HashMap<String, Integer> dd

            = new HashMap<String, Integer>();

       

        // Function Call

        System.out.println(maximumTip(A, B, N, X, Y, dd));

    }

}







OUTPUT:

21

CREDITS: https://www.geeksforgeeks.org/maximum-tip-calculator/