File StockTrading.h

↰ Parent directory (ADS/optimization)

The largest gain of buying and selling a stock with at most k, or with exactly k, transactions, given its prices on n days: a transaction buys on a day b and sells on a later day s, and the transactions do not overlap, :math:` b_1 < s_1 < b_2 < s_2 < cdots < b_k < s_k `.

Definition (ADS/optimization/StockTrading.h)

Detailed Description

The dynamic programming scans the days keeping, for each l <= k, the best balance free[ l ] with l transactions closed and no stock, and the best balance hold[ l ] with the stock of the l-th transaction in hand: on the day of price x, :math:` free[ l ] = max( free[ l ] , hold[ l ] + x ) ` and :math:` hold[ l ] = max( hold[ l ] , free[ l - 1 ] - x ) `, each from the values of the days before (l going down), which keeps the days distinct; O( n k ) time and O( k ) space. The text of the exercise writes the O( k n^2 ) table on the day of the last sale.

With at most k transactions the answer is not negative, and for :math:` k geq n / 2 ` it is the sum of the positive differences of consecutive prices, O( n ); with exactly k the answer may be negative, and there is none for n < 2 k. The case k = 1 is the largest difference :math:` x_s - x_b , s > b, which is the maximum sum segment of the differences [see :ref:`file_ADS_algorithm_MaximumSegments.h].

The contracts [see File Contract.h]: the gain of at most k transactions is not negative. The functions are defined in StockTrading.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

  1. Bentley, Programming Pearls, 2nd ed., Addison-Wesley, 2000, column 8

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions