To become a millionaire

Computer Science Level 2

The various stock prices of an item during various points throughout the day are given in this text . What is the maximum profit you can get if you are allowed to perform at most two buys and at most two sells?

Details and Assumptions

You can only buy another stock if you have sold the one you bought previously.
As an explicit example if the stock prices are [2, 4, 5, 6, 9, 5, 4, 3, 8] you buy at $2$ and sell at $9$ , and you buy another stock at $3$ and sell at $8$ . for a max profit of $12$
[8, 7, 5, 4, 3, 2] there will be no profit, as the value of the stock is decreasing with time.
The stock prices are sequential with respect to time, so that you can only buy or sell only the stock at hand.

Previous programming contest problem

The answer is 189.

2 solutions

Chew-Seong Cheong
Aug 17, 2015

Let the price be $p(n)$ , then the two transactions for maximum profit are:

Buy at $p(33)=p(76)=p(95)=5$ and see at $p(103)=98$ and profit $=93$ . Note that $103 > 95 >76 > 33$ .
Buy at $p(164>103)=3$ and sell at $p(193>164) = 99$ and profit $=96$ .

The total profit is $\boxed{189}$ .

Again I used an Excel spreadsheet.

I never knew spreadsheets could be this handy.

Beakal Tiliksew - 5 years, 10 months ago

Since the list was pretty small just used Ctrl+F. Huehuehue Nice question.

Vishnu Bhagyanath - 5 years, 10 months ago

Piotr Idzik
Apr 17, 2020

I used dynamic programming. Divide the full problem into smaller ones, by considering fewer translations (i.e. in our case only 1) on first $n$ days. They key is to find the relationship, between the profits of the smaller problems and a bigger one (cf. lines 14-16 in the code below).

"""
solution of:
    https://brilliant.org/practice/linear-data-structures-level-4-challenges/?p=2
"""

def max_profit(price_data, max_number_of_transactions):
    res_data = dict()
    def inner(t_num, day_num):
        if t_num <= 0 or day_num <= 0:
            res = 0
        elif (t_num, day_num) in res_data:
            res = res_data[(t_num, day_num)]
        else:
            res = max(inner(t_num, day_num-1),
                      max([price_data[day_num]-price_data[tmp_day]+inner(t_num-1, tmp_day)
                           for tmp_day in range(day_num)]))
            res_data[(t_num, day_num)] = res
        return res
    return inner(max_number_of_transactions, len(price_data)-1)

assert max_profit([8, 7, 5, 4, 3, 2], 2) == 0
assert max_profit([2, 4, 5, 6, 9, 5, 4, 3, 8], 2) == 12
BIG_DATA = [96, 26, 73, 51, 54, 36, 7, 82, 66, 74, 92, 45, 98, 61, 80, 74, 44,
            50, 57, 21, 9, 90, 60, 10, 65, 37, 58, 76, 38, 93, 42, 60, 5, 77,
            61, 66, 17, 84, 92, 52, 34, 63, 21, 93, 55, 33, 48, 91, 36, 90, 26,
            17, 55, 43, 19, 41, 70, 68, 88, 96, 66, 32, 86, 43, 85, 72, 9, 70,
            47, 87, 85, 62, 94, 52, 51, 5, 20, 53, 84, 75, 18, 16, 60, 61, 81,
            89, 91, 49, 37, 27, 6, 19, 76, 20, 5, 77, 26, 62, 7, 17, 80, 28, 98,
            9, 94, 77, 44, 16, 80, 56, 73, 22, 97, 29, 35, 85, 6, 37, 93, 33,
            95, 21, 61, 55, 37, 93, 35, 71, 38, 58, 42, 49, 69, 86, 65, 86, 70,
            35, 90, 30, 81, 6, 81, 83, 89, 75, 6, 91, 59, 86, 13, 10, 63, 85,
            50, 62, 52, 17, 16, 8, 64, 31, 89, 3, 14, 21, 35, 61, 56, 11, 18,
            68, 11, 95, 95, 4, 67, 64, 42, 69, 70, 50, 22, 86, 71, 95, 26, 85,
            23, 44, 79, 93, 99, 50, 90, 26, 72, 65, 28, 72]
print(max_profit(BIG_DATA, 2))

def op(l):
    return max([max(l[i::])-min(l[0:i]) for i in range(1,len(l))])
l=[96, 26, 73, 51, 54, 36, 7, 82, 66, 74, 92, 45, 98, 61, 80, 74, 44, 50, 57, 21, 9, 90, 60, 10, 65, 37, 58, 76, 38, 93, 42, 60, 5, 77, 61, 66, 17, 84, 92, 52, 34, 63, 21, 93, 55, 33, 48, 91, 36, 90, 26, 17, 55, 43, 19, 41, 70, 68, 88, 96, 66, 32, 86, 43, 85, 72, 9, 70, 47, 87, 85, 62, 94, 52, 51, 5, 20, 53, 84, 75, 18, 16, 60, 61, 81, 89, 91, 49, 37, 27, 6, 19, 76, 20, 5, 77, 26, 62, 7, 17, 80, 28, 98, 9, 94, 77, 44, 16, 80, 56, 73, 22, 97, 29, 35, 85, 6, 37, 93, 33, 95, 21, 61, 55, 37, 93, 35, 71, 38, 58, 42, 49, 69, 86, 65, 86, 70, 35, 90, 30, 81, 6, 81, 83, 89, 75, 6, 91, 59, 86, 13, 10, 63, 85, 50, 62, 52, 17, 16, 8, 64, 31, 89, 3, 14, 21, 35, 61, 56, 11, 18, 68, 11, 95, 95, 4, 67, 64, 42, 69, 70, 50, 22, 86, 71, 95, 26, 85, 23, 44, 79, 93, 99, 50, 90, 26, 72, 65, 28, 72]
max([op(l[i::])+op(l[0:i]) for i in range(2,len(l)-1)])

Sahil Goyat - 6 months, 4 weeks ago

I accidentally put '::' instead of ':' in a slice and got the answer to be 190 nvm here is my solution :)

Sahil Goyat - 6 months, 4 weeks ago

I thought of going for the highest possible subarray, and then the splitted subarray recursively, but failed miserably. Didn't expect a Dynamic programming application in the midst of these simple linear problems.

vector<int> max_sub(vector<int>& a, int p, int r) {
    int t_sum = 0, l_indx = 0, r_indx = 0;
    int sum = 0;
    for(int i = p; i <= r; i++) {
        sum = max(sum+a[i], a[i]);
        t_sum = max(sum, t_sum);

        if(t_sum == a[i]) {
            l_indx = r_indx = i;
        } else if(t_sum == sum+a[i])
            r_indx = i;
    }
    return vector<int>({l_indx, r_indx, t_sum});
}

int profit(vector<int>& a) {
    vector<int> d;
    d.push_back(0);
    for(int i = 1; i < a.size(); i++) 
        d.push_back(a[i-1] - a[i]);

    auto s = max_sub(a, 0, a.size()-1);
    auto n = max(max_sub(a, 0, s[0]-1)[2], max_sub(a, s[1]+1, a.size()-1)[2]);

    return max(s[2], s[2]+n);
}

Hossain Nahdi - 1 week, 1 day ago

To become a millionaire

Previous programming contest problem

The answer is 189.

2 solutions

0 pending reports