买卖股票的最佳时机

文章：32. 买卖股票的最佳时机

题目：121. 买卖股票的最佳时机

【思路】

暴力

找最大间距

  • Go实现（不出意外的超时了哈哈）
1
2
3
4
5
6
7
8
9
func maxProfit(prices []int) int {
    res :=0
    for i:=0;i < len(prices);i++{
        for j :=i+1; j < len(prices);j++{
            res = max(res,prices[j] - prices[i])
        }
    }
    return res
}

贪心

找左边最小值和右边最大值即可。

  • Go实现
1
2
3
4
5
6
7
8
9
func maxProfit(prices []int) int {
    leftMin := math.MaxInt
    rightMax :=0
    for i :=0 ;i<len(prices);i++{
        leftMin = min(leftMin,prices[i])
        rightMax = max(rightMax,prices[i]-leftMin)
    }
    return rightMax
}

动态规划

1.确定dp数组及其下标含义

dp[i] [0]：第i天持有股票所得最多现金

dp[i] [1]：第i天不持有股票所得最多现金

2.确定递推公式

如果第i天持有股票即dp[i] [0]，那么可以由两个状态推出来

  • 第i-1天持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i-1] [0]
  • 第i天买入股票，所得现金就是买入今天的股票后所得现金 即：-price[i]

如果第i天不持有股票即dp[i] [1]，也可以由两个状态推出来

  • 第i-1天不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i-1] [1]
  • 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金 即：prices[i] + dp[i-1] [0]

dp[i] [1]取最大的，dp[i] [1] = max(dp[i-1] [i],prices[i] + dp[i-1] [0])

3.数组初始化

dp[i] [0] = max(dp[i-1] [0],-prices[i])

dp[i] [1] = max(dp[i-1] [1],dp[i-1] [0] + prices[i])

可以看出基础都是从dp[0] [0]和dp[0] [1]推导出来的。

dp[0] [0]表示第0天持有股票，此时的持有股票一定是买入股票了，因为不可能有前一天退出来，所以dp[0] [0] -= prices[0]

dp[0] [1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0] [1]=0

4.确定遍历顺序

从递推公式可以看出dp[i]都是由dp[i-1]推导出来的，那么一定是从前向后遍历

5.举例推导。。（上边不理解的话可以画图看看，就能理解了）

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxProfit(int[] prices) {
        //题目只选一次，01背包
        //1.确认dp数组及其下标 ： dp[i][0]为持股第i天的最大收益；dp[i][1]为不持股的第i天所得最多现金
        //2.确认递推公式：dp[i][0]:需要为持有现金最大的 max(dp[i-1][0],-prices[i])  
        //dp[i][1]:收益最大的 max(dp[i-1][1],prices[i]+dp[i-1][0])
        //3.数组初始化: 由上可得都是由dp[0][0]和dp[0][1]推出的
        //dp[0][0] = -prices[0],dp[0][1]=0
        //4.确认遍历顺序：从前到后
        int len = prices.length;
        if(len == 0)return 0;
        int[][]dp = new int[len][2];
        dp[0][0] = -prices[0];
        for(int i = 1 ; i < prices.length;i++){
            dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],prices[i]+dp[i-1][0]);
        }
        return dp[len-1][1];

    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
func maxProfit(prices []int) int {
    dp := make([][]int,len(prices))
    for i:=0 ;i<len(dp);i++{
        dp[i] = make([]int,2)
    }
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    for i :=1 ; i< len(prices);i++{
        dp[i][0] = max(dp[i-1][0],-prices[i])
        dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i])
    } 
    return dp[len(dp)-1][1]
}

买卖股票的最佳时机II

文章：34. 买卖股票的最佳时机II

题目：122. 买卖股票的最佳时机 II

【思路】

和上题的区别在于是本题需要完成多次买卖！

意味着我们需要在递推公式的持股公式进行修改。

第i天持有股票 即dp[i] [0]，如果第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i] [0] = dp[i-1] [1] - prices[i]

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i= 1;i < prices.length;i++){
            dp[i][0] = Math.max(dp[i-1][1] - prices[i], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i]);
        }
        return dp[dp.length-1][1];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
func maxProfit(prices []int) int {
    dp := make([][]int ,len(prices))
    for i := 0 ; i < len(dp);i++{
        dp[i] = make([]int,2)
    }
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    for i :=1 ; i < len(dp);i++{
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])//第一个项是买入
        dp[i][1] = max(dp[i-1][1] , dp[i-1][0] + prices[i])//卖出
    }
    return dp[len(prices)-1][1]
}

【算法总结】

  • 股票问题：买入卖出、持有和不持有的状态下需要区分。
  • 买卖股票的最佳时期II：可以多次买卖，因此dp[i] [0]的推导公式需要注意是从前一状态不持有股票的情况下/与前一状态持有股票保持不变的情况下 取最大值得出。