714.Stock Problem

leetcode

content	time complexity
Naive	$O(2^n*2^n)$
DP step1	$O(n^2)$
DP step2	$O(n)$
Incremental	$O(n)$

Problem Definition

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Naive :sob:

Given size $n$ input, all cases that buy and sell stock prices is $O(2^n*2^n)$.

So, it takes exponetial to find an optimal solution.

Dynamic Programming

Notation prices array be $p$ optimal profits of size $i$ be $c_i$: optimal profits day index from 0 to i-1.

transaction fee $f$

Step1. naive DP :confused:

Suppose that suproblem $c_k$ are optimal where $1 \le k <n$ .

At first, trivially we can notify $c_0 = 0$ because there are no way to sell the stock(base case).

Inductively, we can find size $n$ optimal solution by updating $\forall k$.

Reculsive Formula \(c_i = \begin{cases} 0 & \text{if }i=0 \\ \underset{0 \le k < i}{\operatorname{max}}(c_k, c_k + p_i -p_{k} - f) & \text{if }n \ge 1 \end{cases}\)

Therefore, it takes $O(n^2)$

// Time limited.
// recursive way
int maxProfit(vector<int> &p, int fee) {
    int ans = 0;
    int n = p.size();
    map<int, int> m; //{index, optimal profit}
    ans = lookup(p, fee, n-1, m);
    return ans;
}
int lookup(vector<int>&p, int fee, int i, map<int, int>& m){
    if (i == 0)
        return 0;
    if (m.find(i) != m.end())
        return m[i];
    int loc = 0;
    for (int k = 0; k < i; ++k) {
        loc = max(loc, max(lookup(p, fee, k, m),
                           lookup(p, fee, k, m) + p[i] - p[k] - fee));
    }
    m[i] = loc;
    return loc;
}

// bottom up
int maxProfit_v2(vector<int> &p, int fee) {
    int n = p.size();
    int *m = new int[n];
    m[0] = 0;
    for (int i = 0; i < n; ++i) {
        m[i] = 0;
        for (int k = 0; k < i; ++k) {
            m[i] = max(m[i], max(m[k], m[k] + p[i] - p[k] - fee));
        }
    }
    int ans = m[n-1];
    delete[] m;
    return ans;
}

Step2. smart DP :smile:

reference

# TODO

Incremental :satisfied:

detail

When updating k in [1, n), if transaction margin is good, do it!
By keeping(possibly buying) a minimum price for each iteration, if margin is good, the transaction is one of the optimal solution. so, sell the stock, and update minimum price to prevent rising the stock continuously(in this situation, update the minimum price considering offset fee. To be more specific, let minimum price be current price - fee).
for example, given a fee 1, if a sequence of price is that 0, 2, 4, ...
the ans = 0 + 2 - 0 - 1 + 4 - (2 - 1) - 1 = 4 - 1 = 3! Look at this picture in order to capture the principal intuitively!

c++ version implementation

int maxProfit_v3(vector<int> &p, int fee) {
    int n = p.size();
    if (n < 1) {
        return 0;
    }
    int ans = 0; // total profits.
    int min_p = p[0]; // keep the first stock.
    for (int i = 0; i < n; i++) {
        if (p[i] < min_p)
            min_p = p[i]; // keep a minimum price incrementally.
        else if (p[i] > min_p + fee) { // if margin is good.
            ans += (p[i] - min_p - fee); // buy the stored min_p, sell it.
            min_p = p[i] - fee; // update minimum price to offset fee.
        }
    }
    return ans;
}