原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

解法1:

贪心

只要是股票上涨日 就进行买卖那就必赚
只用算隔天涨幅赚的钱即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int ans = 0;
        for(int i = 0 ; i < n - 1 ; i++){
            int tmp = prices[i + 1] - prices[i];
            if(tmp > 0){
                ans += tmp;
            }
        }

        return ans;
    }
}

解法2:

动态规划

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
/**
 *  f[i][j] 表示 第i天的持股状态为j时的最大现金数   j = 1 表示持有股票
 *  初始时
 *  1. 如果不进行任何操作 f[0][0] = 0 第一天不交易所以没利润
 *  2. 如果进行交易 f[0][1] = -prices[1] 交易了股票 则要付出现金
 *
 *  状态转移
 *  第 i 天 买入 或 不操作 f[i][1] = max(f[i - 1][1],f[i - 1][0] - prices[i])
 *  第 i 天 卖出 或 不操作 f[i][0] = max(f[i - 1][0],f[i - 1][0] + prices[i])
 */
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int [][] f = new int[n + 1][2];
        // 不操作 则 现金为0
        f[0][0] = 0;
        // 第1天手上没持股则只能买入
        f[0][1] = -prices[0];
        
        for(int i = 1 ; i < n ; i++){
            // 卖出 或者 不操作
            f[i][0] = Math.max(f[i - 1][1] + prices[i],f[i - 1][0]);
            // 买入 或者 不操作
            f[i][1] = Math.max(f[i - 1][0] - prices[i],f[i - 1][1]);
        }
        
        return  Math.max(f[n - 1][0],f[n - 1][1]);
    }
}

更进一步的可以在空间上进行优化

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
/**
 * 空间优化
 * 先考虑将状态数组分开表示 将表示状态维度省去 (这个操作并没有优化空间)
 */
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 表示第i天所持有的最大现金
        int [] cash = new int[n];
        // 表示第i天是否持有股票
        int [] hold = new int[n];
        
        // 初始值
        // 刚开始只能买入 所以可获得的最大现金为0 
        cash[0] = 0;
        // 刚开始为持有状态 则只能买入
        hold[0] = -prices[0];
 
        for(int i = 1 ; i < n ; i++){
            // 不操作 或者 卖出  这只会影响到cash 因为卖出一定是赚的
            // 且只有在股票持有的状态才能卖出
            cash[i] = Math.max(cash[i - 1],hold[i - 1] + prices[i]);  

            // 不操作 或者 买入 这只会影响hold 因为买入一定是花钱的
            // 通过持有现金才能买入
            hold[i] = Math.max(hold[i - 1],cash[i - 1] - prices[i]);
        }
        
        return cash[n - 1];
    }
}

在上一步基础可以观察到 cash 和 hold都只涉及到上一步的变量因此 我们可以用滚动数组进一步优化

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
/**
 * 空间优化
 * 先考虑将状态数组分开表示 将表示状态维度省去 (这个操作并没有优化空间)
 */
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 表示第i天所持有的最大现金
        int cash = 0 ;
        // 表示第i天是否持有股票
        int hold = 0;
        
        // 初始值
        // 刚开始只能买入 所以可获得的最大现金为0 
        cash = 0;
        // 刚开始为持有状态 则只能买入
        hold = -prices[0];

        int preCash = cash;
        int preHold = hold;

        for(int i = 1 ; i < n ; i++){
            // 不操作 或者 卖出  这只会影响到cash 因为卖出一定是赚的
            // 且只有在股票持有的状态才能卖出
            cash = Math.max(preCash,preHold + prices[i]);  

            // 不操作 或者 买入 这只会影响hold 因为买入一定是花钱的
            // 通过持有现金才能买入
            hold = Math.max(preHold,preCash - prices[i]);

            // 更新状态
            preCash = cash;
            preHold = hold;
        }
        
        return cash;
    }
}