1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <sstream>

std::stringstream ss(std::stringstream::out);

//  h - has how many unit stock
//  p - profit
//  bp - best profit
void dfs(std::string t, std::string& s,
         double* P, int x, int y, int h, double p, double &bp) {
    if(x == y) {
        if(p > bp) {
            bp = p;
            s = t;
        }
    } else {
        if(h > 0) {
            //  have stock can sell
            ss.clear();
            ss.str("");
            ss << P[x];
            std::string sell = ss.str() + " sell\n";
            dfs(t + sell, s, P, x + 1, y, 0, p + h * P[x], bp);
        }

        //  buy
        ss.clear();
        ss.str("");
        ss << P[x];
        std::string buy = ss.str() + " buy\n";
        dfs(t + buy, s, P, x + 1, y, h + 1, p - P[x], bp);

        //  pass
        ss.clear();
        ss.str("");
        ss << P[x];
        std::string pass = ss.str() + " pass\n";
        dfs(t + pass, s, P, x + 1, y, h, p, bp);
    }
}

int main() {

    double prices[8] = {55.39, 109.23, 48.29, 81.59,
                        81.58, 105.53, 94.45, 12.24};

    double bestTotalProfit = 0.0;

    std::string ans, tmp;

    dfs(tmp, ans, prices, 0, 8, 0, 0.0, bestTotalProfit);

    std::cout << bestTotalProfit << std::endl;
    std::cout << ans;

    return 0;
}