Skip to content

Latest commit

 

History

History
144 lines (123 loc) · 5.19 KB

README.md

File metadata and controls

144 lines (123 loc) · 5.19 KB

Say you have an array 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 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).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

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

Related Topics:
Dynamic Programming

Similar Questions:

Solution 1. DP

Let buy[i+1][k] be the max balance with A[0..i] after exactly k buys. buy[i+1][k] is initialized with -Inf. Let sell[i+1][k] be the max balance with A[0..i] after exactly k sells. sell[i+1][k] is initialized with 0.

buy[i+1][k] = max(
                    buy[i][k],             // skip A[i]
                    sell[i][k-1] - A[i]  // buy A[i]
                )
sell[i+1][k] = max(
                    sell[i][k],           // skip A[i]
                    buy[i][k] + A[i]    // sell A[i]
                )
        where i+1 >= k

The answer is MAX( sell[N][k] ) where 0 <= k <= K

// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv
// Author: github.com/lzl124631x
// Time: O(NK)
// Space: O(NK)
class Solution {
public:
    int maxProfit(int K, vector<int>& A) {
        int N = A.size(), ans = 0;
        vector<vector<int>> buy(N + 1, vector<int>(K + 1, INT_MIN)), sell(N + 1, vector<int>(K + 1));
        for (int i = 0; i < N; ++i) {
            for (int k = 1; k <= min(i + 1, K); ++k) {
                buy[i + 1][k] = max(buy[i][k], sell[i][k - 1] - A[i]);
                sell[i + 1][k] = max(sell[i][k], buy[i][k] + A[i]);
                ans = max(ans, sell[i + 1][k]);
            }
        }
        return ans;
    }
};

Solution 2. DP Space Optimization

buy[i+1][k] = max(
            buy[i][k],           // skip A[i]
            sell[i][k-1] - A[i]  // buy A[i]
        )
sell[i+1][k] = max(
            sell[i][k],           // skip A[i]
            buy[i+1][k] + A[i]    // sell A[i]
                 ^
                 └-- Here changing buy[i][k] to buy[i+1][k] is fine because buying and selling at A[i] is simply no-op.
        )

We can see that buy[i+1][k] depands on buy[i][k] and sell[i][k-1], sell[i+1][k] depands on sell[i][k] and buy[i+1][k]. We can remove the first dimension of buy and sell arrays, reducing the space complexity from O(KN) to O(K).

// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv
// Author: github.com/lzl124631x
// Time: O(KN)
// Space: O(K)
class Solution {
public:
    int maxProfit(int K, vector<int>& A) {
        int N = A.size(), ans = 0;
        vector<int> buy(K + 1, INT_MIN), sell(K + 1);
        for (int i = 0; i < N; ++i) {
            for (int k = 1; k <= min(i + 1, K); ++k) {
                buy[k] = max(buy[k], sell[k - 1] - A[i]);
                sell[k] = max(sell[k], buy[k] + A[i]);
                ans = max(ans, sell[k]);
            }
        }
        return ans;
    }
};

Solution 3. Alien Trick

// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
// Author: github.com/lzl124631x
// Time: O(Nlog(max(P)))
// Space: O(1)
// Ref: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/463598/Python-short-O(NlogW)-solution-with-alien-trick
class Solution {
    vector<int> maxProfitWithFee(vector<int> &A, int fee) {  // maxProfit, corresponding number of transactions
        vector<int> best{-A[0], 0}, current{0, 0};
        for (int i = 1; i < A.size(); ++i) {
            if (A[i] + best[0] - fee > current[0]) current = {A[i] + best[0] - fee, 1 + best[1]};
            if (current[0] - A[i] > best[0]) best = {current[0] - A[i], current[1]};
        }
        return current;
    }
public:
    int maxProfit(int k, vector<int>& A) {
        if (A.empty()) return 0;
        int L = 0, R = *max_element(begin(A), end(A));
        return calc(l)[0] + l * k 
        while (L <= R) {
            int M = (L + R) / 2;
            if (maxProfitWithFee(A, M)[1] > k) L = M + 1;
            else R = M - 1;
        }
        return maxProfitWithFee(A, L)[0] + L * k;
    }
};