WineProblem.java

packagecom.thealgorithms.dynamicprogramming;

/**
 * The WineProblem class provides a solution to the wine selling problem.
 * Given a collection of N wines with different prices, the objective is to maximize profit by selling
 * one wine each year, considering the constraint that only the leftmost or rightmost wine can be sold
 * at any given time.
 *
 * The price of the ith wine is pi, and the selling price increases by a factor of the year in which
 * it is sold. This class implements three approaches to solve the problem:
 *
 * 1. **Recursion**: A straightforward recursive method that computes the maximum profit.
 * - Time Complexity: O(2^N)
 * - Space Complexity: O(N) due to recursive calls.
 *
 * 2. **Top-Down Dynamic Programming (Memoization)**: This approach caches the results of subproblems
 * to avoid redundant computations.
 * - Time Complexity: O(N^2)
 * - Space Complexity: O(N^2) for the storage of results and O(N) for recursion stack.
 *
 * 3. **Bottom-Up Dynamic Programming (Tabulation)**: This method builds a table iteratively to
 * compute the maximum profit for all possible subproblems.
 * - Time Complexity: O(N^2)
 * - Space Complexity: O(N^2) for the table.
 */
publicfinalclassWineProblem {
privateWineProblem() {
 }

/**
 * Calculate maximum profit using recursion.
 *
 * @param arr Array of wine prices.
 * @param si Start index of the wine to consider.
 * @param ei End index of the wine to consider.
 * @return Maximum profit obtainable by selling the wines.
 */
publicstaticintwpRecursion(int[] arr, intsi, intei) {
intn = arr.length;
intyear = (n - (ei - si + 1)) + 1;
if (si == ei) {
returnarr[si] * year;
 }

intstart = wpRecursion(arr, si + 1, ei) + arr[si] * year;
intend = wpRecursion(arr, si, ei - 1) + arr[ei] * year;

returnMath.max(start, end);
 }

/**
 * Calculate maximum profit using top-down dynamic programming with memoization.
 *
 * @param arr Array of wine prices.
 * @param si Start index of the wine to consider.
 * @param ei End index of the wine to consider.
 * @param strg 2D array to store results of subproblems.
 * @return Maximum profit obtainable by selling the wines.
 */
publicstaticintwptd(int[] arr, intsi, intei, int[][] strg) {
intn = arr.length;
intyear = (n - (ei - si + 1)) + 1;
if (si == ei) {
returnarr[si] * year;
 }

if (strg[si][ei] != 0) {
returnstrg[si][ei];
 }
intstart = wptd(arr, si + 1, ei, strg) + arr[si] * year;
intend = wptd(arr, si, ei - 1, strg) + arr[ei] * year;

intans = Math.max(start, end);
strg[si][ei] = ans;

returnans;
 }

/**
 * Calculate maximum profit using bottom-up dynamic programming with tabulation.
 *
 * @param arr Array of wine prices.
 * @throws IllegalArgumentException if the input array is null or empty.
 * @return Maximum profit obtainable by selling the wines.
 */
publicstaticintwpbu(int[] arr) {
if (arr == null || arr.length == 0) {
thrownewIllegalArgumentException("Input array cannot be null or empty.");
 }
intn = arr.length;
int[][] strg = newint[n][n];

for (intslide = 0; slide <= n - 1; slide++) {
for (intsi = 0; si <= n - slide - 1; si++) {
intei = si + slide;
intyear = (n - (ei - si + 1)) + 1;
if (si == ei) {
strg[si][ei] = arr[si] * year;
 } else {
intstart = strg[si + 1][ei] + arr[si] * year;
intend = strg[si][ei - 1] + arr[ei] * year;

strg[si][ei] = Math.max(start, end);
 }
 }
 }
returnstrg[0][n - 1];
 }
}