LeetCode 188 Best Time to Buy and Sell Stock IV (C++)

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


Solution


 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
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        const int N = prices.size();
        if (N == 0) return 0;
        if (k >= N-1) {
            int ret = 0;
            for (int i = 1; i < N; ++i) {
                if ((prices[i] - prices[i - 1]) > 0) {
                    ret += prices[i] - prices[i - 1];
                }
            }
            return ret;
        }
        // maxProfits[i][j] max profits at most i transactions from day 0 to day j
        vector<vector<int>> maxProfits(k + 1, vector<int>(N, 0));

        // maxProfits[0][?] = 0
        // maxProfits[?][0] = 0
        for (int i = 1; i <= k; ++i) {
            int tmp = -prices[0];
            for (int j = 1; j < N; ++j) {
                maxProfits[i][j] = max(maxProfits[i][j - 1], prices[j] + tmp);
                tmp = max(tmp, maxProfits[i-1][j] - prices[j]);
            }
        }
        return maxProfits[k][N - 1];
    }
};

Popular posts from this blog

How Django Works (4) URL Resolution

Python Class Method and Class Only Method

How Django Works (2) Built-in Server, Autoreload