New to Rust? Grab our free Rust for Beginners eBook Get it free →
Wines Problem Dynamic Programming in C++

The wines problem asks you to sell one bottle from either end of a row each year, with the sale year multiplying its price. Dynamic programming solves it by storing the best revenue for each interval of bottles still in the row.
In this piece, I’ll show how to calculate that best value and compile and run the C++ solution.
TL;DR
For the wines problem, define each subproblem by the remaining interval and choose its left or right bottle using the year determined by the interval length.
- For interval [left, right], year = n – (right – left).
- Take the larger of year × price[left] + dp[left + 1][right] and year × price[right] + dp[left][right – 1].
- Tabulation runs in O(n²) time and uses O(n²) memory.
What is the wines problem?
For initial prices p[0..n – 1], choose left or right each year to maximize Σ(t × p[jt]) for t = 1 through n, where jt is the zero-based position sold in year t.
| Term | Meaning in the implementation |
|---|---|
| price[i] | Original input price at zero-based position i. The vector is read-only. |
| dp[left][right] | Best revenue obtainable from the inclusive remaining interval. |
| Empty child | Contributes zero to a one-bottle transition. No empty interval is stored in the table. |
After every sale, the bottles left unsold still occupy one contiguous interval. This lets the solution track the remaining range with its two endpoint indices.
How an early sale changes later choices
A low first-year price is only part of the result because that sale determines which bottles set the next endpoints.
For prices [2, 3, 5, 1, 4], repeatedly taking the cheaper endpoint gives 2, 3, 4, 1, 5 and revenue 49. The interval solution can choose 2, 4, 1, 3, 5 for revenue 50.
| Choice rule | Sale order | Revenue calculation | Total |
|---|---|---|---|
| Cheaper endpoint each year | 2, 3, 4, 1, 5 | 1×2 + 2×3 + 3×4 + 4×1 + 5×5 | 49 |
| Best continuation at each interval | 2, 4, 1, 3, 5 | 1×2 + 2×4 + 3×1 + 4×3 + 5×5 | 50 |
What does a DP state represent?
Let dp[left][right] store the best revenue for the inclusive interval from left to right. Its next sale year is n – (right – left), where n is the original bottle count. This year depends on the interval length, not on the history of endpoint choices, so the pair of bounds is enough to identify a state.
| Remaining interval | Bottles left | Next sale year |
|---|---|---|
| [0, 4] | 5 | 1 |
| [1, 4] | 4 | 2 |
| [2, 3] | 2 | 4 |
| [3, 3] | 1 | 5 |
For a one-bottle interval, the conditional lookup supplies zero for its empty child, leaving its only sale as the score. Assume every interval of length L – 1 already stores its maximum. Any plan for length L starts at one endpoint and leaves one of those shorter ranges, so the two candidates cover every possible first move and the larger total is optimal.
Because future choices depend only on the shared interval, store its best suffix once and reuse that value across all sale histories.
| Interval length | Year multiplier | Sample state values |
|---|---|---|
| 1 | 5 | 10, 15, 25, 5, 20 |
| 2 | 4 | 23, 37, 29, 24 |
| 3 | 3 | 43, 40, 41 |
| 4 | 2 | 45, 48 |
| 5 | 1 | 50 |
Each row lists its intervals from left to right. For prices 5 and 1, selling 5 first earns 4×5 + 5 = 25, while selling 1 first earns 4×1 + 25 = 29.
The other length-two values follow the same calculation. For prices 2 and 3, taking 2 first gives 4×2 + 15 = 23, which beats 4×3 + 10 = 22. For prices 3 and 5, the candidates are 4×3 + 25 = 37 and 4×5 + 15 = 35, so that cell stores 37.
| Interval | Sell left first | Sell right first | Best value |
|---|---|---|---|
| [0, 2] | 3×2 + 37 = 43 | 3×5 + 23 = 38 | 43 |
| [1, 3] | 3×3 + 29 = 38 | 3×1 + 37 = 40 | 40 |
| [2, 4] | 3×5 + 24 = 39 | 3×4 + 29 = 41 | 41 |
| [0, 3] | 2×2 + 40 = 44 | 2×1 + 43 = 45 | 45 |
| [1, 4] | 2×3 + 41 = 47 | 2×4 + 40 = 48 | 48 |
These intermediate cells contribute to the full interval’s final score. When checking a hand trace, compare the diagonal first, then the shorter intervals, and finish with dp[0][n – 1]. That order helps isolate an incorrect sale year from a bad boundary index or final lookup.
For the full row, the first sale on the left gives 1×2 + 48 = 50. Starting from the right gives 1×4 + 45 = 49, so the answer is the left candidate.
How to solve the wines problem in C++ step by step
The following source translates the interval recurrence into a bottom-up C++ table.
Step 1: Write the interval recurrence
year = n - (right - left)
dp[left][right] = max(
year * price[left] + dp[left + 1][right],
year * price[right] + dp[left][right - 1]
)
For a multi-bottle interval, selling left leaves [left + 1, right], while selling right leaves [left, right – 1]. A singleton has two empty child ranges, so both guarded lookups contribute zero and its diagonal cell is year × price[left]. The conditions avoid reading a cell outside the matrix.
Step 2: Fill intervals by increasing length
for (int length = 1; length <= n; ++length) {
const long long year = n - length + 1;
for (int left = 0; left + length <= n; ++left) {
const int right = left + length - 1;
// Compute dp[left][right] from its shorter intervals.
}
}
For a fixed length, left runs from 0 through n – length, so right = left + length – 1 never exceeds n – 1. This visits every valid interval of that length and leaves the lower triangle unused. Each recurrence reads intervals one bottle shorter, completed in an earlier pass, so updates in this pass cannot change its candidates.
An uncached recursive search can recompute an interval after different early choices, so a top-down version caches each endpoint pair with a separate visited flag. Avoid a numeric sentinel such as -1 unless the input limits prove it cannot be a valid answer, especially with signed prices. The cache uses O(n²) space, and recursion can reach O(n) depth.
Step 3: Compile and run the C++ implementation
I compiled the source with g++ 13.3.0 and ran the sample input below. It printed a maximum profit of 50 with exit code 0.
#include <algorithm>
#include <iostream>
#include <vector>
long long max_profit(const std::vector<long long>& price) {
const int n = static_cast<int>(price.size());
if (n == 0) return 0;
std::vector<std::vector<long long>> dp(
n, std::vector<long long>(n, 0));
for (int length = 1; length <= n; ++length) {
const long long year = n - length + 1;
for (int left = 0; left + length <= n; ++left) {
const int right = left + length - 1;
const long long sell_left = year * price[left] +
(left + 1 <= right ? dp[left + 1][right] : 0);
const long long sell_right = year * price[right] +
(left <= right - 1 ? dp[left][right - 1] : 0);
dp[left][right] = std::max(sell_left, sell_right);
}
}
return dp[0][n - 1];
}
int main() {
int n;
if (!(std::cin >> n) || n < 0) return 1;
std::vector<long long> price(n);
for (long long& value : price) {
if (!(std::cin >> value)) return 1;
}
std::cout << "Maximum profit: " << max_profit(price) << '\n';
}
Build the source file with this C++17 command:
g++ -std=c++17 -Wall -Wextra -pedantic wines_problem.cpp -o wines_problem
Run the compiled program with the sample input piped to standard input:
printf '5\n2 3 5 1 4\n' | ./wines_problem
The executed program prints this exact result:
Maximum profit: 50

The screenshot shows this exact command and result with exit code 0, matching the sample interval table.
The function takes the price vector by const reference, so it reads the original prices without copying the full input. It returns the full interval’s profit, while main handles input and output.
Edge cases and complexity
Across all lengths, the n(n + 1) / 2 valid intervals each compare two constant-time candidates, so the work is O(n²).
The square table allocates n² cells for O(n²) memory, including unused lower-triangle cells. The full table is the clearest choice here because every interval value remains available for inspection.
| Case | Symptom | Fix in this implementation |
|---|---|---|
| Zero bottles | There is no valid table index. | Return zero before allocating or indexing dp. |
| Single bottle | Both endpoint choices refer to the same item. | Use the year-one sale, and treat the empty child as zero. |
| Malformed input | The count or a required price cannot be read. | Exit with status 1 before printing a result. |
| Large revenue | A product or accumulated total may exceed long long. | Use a wider representation when the task bounds require it. |
The input loop expects one nonnegative bottle count followed by that many prices. It does not expect a leading test-case count, and it rejects a negative count or missing price with exit status 1 instead of printing a partial result. A zero count returns zero before the table is indexed, although a judge may require at least one bottle.
The boundary tests exercise three separate paths:
- Use a zero bottle count to exercise the empty-range return.
- Use one bottle to exercise the diagonal state.
- Omit a required price to exercise input failure.
For T cases with lengths ni, process one fresh vector and table at a time. Total work is O(sum of ni2) and peak table memory is O(max of ni2).
No maximum n or price is stated, so check that the largest year × price term and final total fit in long long. If the constraints need a wider type, cast an operand before multiplying because assigning an already-overflowed result to long long cannot restore it.
| Problem variant | Adjustment |
|---|---|
| Negative bottle prices | The recurrence still applies when every bottle must be sold, and a signed type must fit every product and total. |
| Early stopping allowed | Add a stop option to each state and use the variant’s sale-year rule. |
| Return the sale order | Save the winning endpoint for each state and follow those choices from [0, n – 1]. |
| Tie-breaking required | Apply the stated rule when both endpoint candidates have equal value. |
The standard version requires every bottle to be sold, so negative prices remain part of the total. Add a zero-revenue stop choice only when the statement permits early stopping, since otherwise it changes the problem’s answer.
std::vector gives this standard C++ implementation storage sized from the input count. A fixed array such as 100 by 100 sets its own row-length cap, independent of the judge’s limit.
- For score-only output, a rolling vector uses O(n) memory. Update left indices in increasing order and read dp[left + 1] before overwriting the current cell, because that entry still holds the shorter-interval value. The value at dp[left] also remains from the previous length until its assignment. This saves space but loses the full trace.
- For a sale order, save each winning endpoint and follow the choices from [0, n – 1], shrinking the interval after each sale and applying the required tie rule.
Conclusion: choose from the interval ends
For the sample row [2, 3, 5, 1, 4], the state table and compiled program both give a maximum profit of 50.
To compare this interval problem with another end-choice recurrence, read CodeForGeek’s optimal game strategy in C++. For another bottom-up recurrence example, see the friends pairing problem in C++. The C++ references for std::vector and numeric_limits document the containers and integer limits used here.
FAQ
These answers cover two common follow-up questions about the implementation and its cost.
Does the wines problem require recursion?
No. The recurrence can be evaluated with top-down memoization or bottom-up tabulation. This C++ program uses bottom-up tabulation, filling shorter intervals first.
Why is the wines problem O(n²)?
A state is one interval [left, right]. There are n(n + 1) / 2 valid intervals, and each compares two endpoint choices in constant time, so the total time is O(n²). The stored table also uses O(n²) space.




