1
2
3
4

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

1
2
3
4
5

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

1
2
3

输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

 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
58
59
60
61
62
63
64
65
66
67
68
69
70

//
struct Solution;

// @lc code=start
use std::cmp;

impl Solution {
    /// ## 解题思路:
    /// - 动态规划+贪心
    /// 1. 设 profit[i]: 投资者从第i天开始到最后的最终投资收益;
    /// 2. 投资者每天存在2种状态:
    ///    - 未投资(uninvested):
    ///    - 已投资(invested);
    /// 3. 投资者每天可以有不同投资策略, 以获得最大利润:
    ///    - 未投资(uninvested), 此时有两种投资策略:
    ///       - 不操作. 此时当天投资收益为0, 后续投资收益为: profit[i+1].未投资;
    ///       - 买入. 此时当天投资收益为: -prices[i], 后续投资收益为: profit[i+1].已投资;
    ///       最大收益为: max(0+profit[i+1].未投资, profit[i+1].已投资 - prices[i])
    ///    - 已投资(invested), 此时也有2总策略:
    ///       - 不操作. 此时当天投资收益为: 0, 后续投资收益为: profit[i+1].已投资;
    ///       - 卖出. 此时当天投资收益为: prices[i]. 后续投资收益为: profit[i+1].未投资
    ///       最大收益为: max(profit[i+1].已投资, profit[i+1].未投资 + prices[i])
    /// 4. 最终最大收益为: profit[0].未投资
    ///    初始条件: profit[n]: (0, 0)
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let K = 2;
        let n = prices.len();
        let mut profit = vec![(0, 0); K + 1];
        for &p in prices.iter().rev() {
            for k in 1..=K {
                profit[k].0 = profit[k].0.max(-p + profit[k].1);
                profit[k].1 = profit[k].1.max(p + profit[k - 1].0);
            }
        }
        profit[K].0
    }

    /// ## 解题思路：
    /// 第i天，共有5种操作：
    /// 1. 无操作；
    /// 2. 第1次买入；
    /// 3. 第1次卖出；
    /// 4. 第2次买入；
    /// 5. 第2次卖出；
    ///
    /// 其中第1种操作不会产生任何利润，后面4次操作最大利润递推公式分别如下：
    /// 1. buy1(i) = max(buy1(i-1), -prices[i])， 注意: buy1(i-1)：表示[0, i-1]执行了一次买入操作的最大利润, 则第i天将不执行买入操作；-prices[i]表示第i天执行买入操作，所以利润为负；
    /// 2. sell1(i) = max(sell1(i-1), buy1(i-1)+prices[i]), 第i天第1次卖出操作的最大利润为：不操作，此时最大利润为前一天第一次卖出最大利润或第一次卖出，最大利润和
    /// 3. buy2(i) = max(buy2(i-1), sell1(i-1)-prices[i])
    /// 3. sell2(i) = max(sell2(i-1), buy2(i-1)+prices[i])
    pub fn max_profit2(prices: Vec<i32>) -> i32 {
        if prices.len() < 2 {
            return 0 as i32;
        }
        let mut buy1 = 0 - prices[0]; // 第一次买入后的收益(第一次买入前手中没有股票, 也没有参与过买卖,)
        let mut sell1 = 0; // 第一次卖出后的收益(卖出前手中的股票为0)
        let mut buy2 = -prices[0]; // 第二次买入后的收益
        let mut sell2 = 0; // 第二次卖出后的收益
        for i in 1..prices.len() {
            buy1 = cmp::max(buy1, -prices[i]);
            sell1 = cmp::max(sell1, buy1 + prices[i]);
            buy2 = cmp::max(buy2, sell1 - prices[i]);
            sell2 = cmp::max(sell2, buy2 + prices[i]);
        }

        sell2
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        #第一次买入后利润
        profile_1_in = 0 - prices[0]
        #第一次卖出后利润
        profile_1_out = 0
        #第二次买入后利润
        profile_2_in = 0 - prices[0]
        #第二次卖出后利润
        profile_2_out = 0
        for p in prices[1:]:
            profile_2_out = max(profile_2_out, p + profile_2_in)
            profile_2_in = max(profile_2_in, profile_1_out - p)
            profile_1_out = max(profile_1_out, profile_1_in + p)
            profile_1_in = max(profile_1_in, -p)
        return profile_2_out