LeetCode股票类问题研究

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

1 2 3 4

Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

1 2 3

Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.

该问题即为求解在前i个元素的最小值处买入，在prices[i]处卖出，遍历数组求最大利润。

Say you have an array prices 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 as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4
5

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1
2
3

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

为了获得最大利润，我可以在每一个有利可图的时候买入再卖出，也就是只要prices[i] > prices[i - 1]我就进行一次买入卖出的操作

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 twotransactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

1 2 3 4

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

Example 2:

1 2 3 4 5

Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1 2 3

Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.

两次买卖，遍历prices数组，当遍历到第i个元素时，可以用lc121的方法求得前i个元素用一次买卖得到的最大利润，假设从这个元素之后开始第二次买卖，则也可以用上述方法求得第二次买卖的最大利润，其中每一次的买入价格从prices[i]变为prices[i] - maxProfit1

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:

1 2 3

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:

1 2 3 4

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.

类似买卖股票问题3的想法，只要在前一次买卖的基础上有利可图就买入。

p.s. 当k比prices数组的长度大的时候，应该采用买卖股票2的方式解决，这样只需要O(n)的复杂度。

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

1 2 3

Input: [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]

• Approach 1

DP，dp[i]表示prices[i…n]的最大利润，dp[i] = max(dp[i + 1], max(dp[j + 2] + prices[j] - prices[i]))，for all j > i

• Approach 2


DP + 自动机

Sold = held + price

held = max(held, reset - price)

Reset = max(reset, sold)

• Approach 1

1
2
3
4
5
6
7
8
9
10
11
12
13

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<int> dp(n + 2, 0);
    for(int i = n - 1; i >=0; i--){
        int c1 = 0;
        for(int j = i + 1; j < n; j++){
            c1 = max(c1, dp[j + 2] + prices[j] - prices[i]);
        }
        int c2 = dp[i + 1];
        dp[i] = max(c1, c2);
    }
    return dp[0];
}

• Approach 2

1
2
3
4
5
6
7
8
9
10

int maxProfit(vector<int>& prices) {
    int sold = INT_MIN, held = INT_MIN, reset = 0;
    for(int p: prices){
        int pre = sold;
        sold = held + p;
        held = max(reset - p, held);
        reset = max(pre, reset);
    }
    return max(sold, reset);
}

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.

Example 1:

1 2 3 4

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: Buying at prices[0] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

类似上一题的做法，但是只有两个状态，sold和held

sold = max(sold, held + prices[i] - fee)

held = max(held, sold - prices[i])

注意此处初始化的时候，sold = 0，而held应该赋值为-prices[0]，相当于表示在i=0处的sold和held值的情况，也就是在i=0时已经卖出股票，则收益为0；在i=0时持有股票，则只能是买入了prices[0]的股票，因此收益为-prices[0]；所有的fee均在卖出股票时候计算，因为最终手里的股票必须要全部卖出才是最划算的情况。