0
$\begingroup$

Problem Statement:

Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Here's the link to the problem.


I know the solution to this problem but what I'd like to know is how do I write the total profit, (i.e. the thing that we are trying to maximize,) as a mathematical expression? I tried the following (where $n$ is the length of the list):

$$\sum_{ \substack{1 \leq i,j \leq n \\ i\lt j}} (x_j - x_i)[i,j \text{ unique}] $$

But this would be wrong since it could include both $i = 1, j = 2$ and $i = 2, j = 3$, and we can't both buy and sell a stock on day 2. Also I had to resort to the Iversonian notation for this, and if possible, I'd like to avoid it.

I don't know if I should be needing two variables for the summation, since we only iterate through the list once for calculating the profit, but I couldn't do it in one variable.

PS: This is my first time posting here and I couldn't really decide on the tags for this problem. Pardon me if they are wrong, and let me know which ones to use and I'll update the question. :)

$\endgroup$
1
$\begingroup$

To write the profit as a mathematical expression, you need to set up a little more notation for the buys and sells. Let $x[1], \ldots, x[n]$ be the stock prices on days $1, \ldots, n$. For each buy and sell, let $b$ denote the day on which the stock is bought, and $s$ the day on which it is sold. The problem says that we must have $1 \leq b < s \leq n$. The profit from this single transaction is $P = x[s] - x[b]$.

However, the problem allows many buys and sells, say $(b_1, s_1), \ldots, (b_k, s_k)$ for some numbers which must satisfy $$1 \leq b_1 < s_1 < b_2 < s_2 < \cdots < b_k < s_k \leq n.$$ The total profit from these $k$ transactions is $$ P = \sum_{i = 1}^k \left(x[b_i] - x[s_i]\right). $$ Of course the tricky part is that you don't know ahead of time what $k$ should be, so you're not only trying to optimise over the $b_i$ and $s_i$ variables, but also $k$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for the answer! This really is very smart. I knew I didn't have to sum over two variables, but it never came to me that I could iterate over the stocks and have separate notations for buying and selling. You're awesome! :) $\endgroup$ – BK1603 Sep 29 '20 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.