LeetCode百题【买卖股票的最佳时机I,II,III】

题目描述

解法

贪心
- 求最大利润，及为求卖出和买入的最大差值
- 只要不亏钱就买卖

class Solution {
    public int maxProfit(int[] prices) {
        int result=0;
        for (int i = 1; i <= prices.length-1; i++) {
            if(prices[i]>prices[i-1]){
                //只要今天比昨天要高就进行买卖
                result+=prices[i]-prices[i-1];
            }
        }
        return result;
    }
}

时间复杂度 O(n)

来源：力扣（LeetCode）
链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn.com)

题目描述

解法

动态规划

转移方程

```
dp[i]=max(dp[i-1),price[i]-minPrice)


- **我们每次遍历的时候不仅要看当前数，还要维护之前的最小数**

```java
class Solution {
    public int maxProfit(int[] prices) {
       int result=0;
        int minNum=prices[0];
        for (int i = 1; i < prices.length; i++) {
            result=Math.max(result,prices[i]-minNum);
            minNum=Math.min(minNum,prices[i]);
        }
        return result;
    }
}

时间复杂度O(n)

来源：力扣（LeetCode）
链接：121. 买卖股票的最佳时机 - 力扣（LeetCode） (leetcode-cn.com)

题目描述

解法

动态规划
- dp[i]表示第 i天结束之后的「累计最大收益」
- 题目描述我们最多同时买入一支股票，因此我们会有三种状态
  - 我们目前持有一支股票，对应的「累计最大收益」记为 dp[i] [0]
  - 我们目前不持有股票，处于冷冻期中,「累计最大收益」记为 dp[i] [1]
  - 我们目前不持有股票，不处于冷冻期中,「累计最大收益」记为 dp[i] [2]
对于dp[i] [0]
1. 这张股票可以是之前持有的，今天不做任何买卖
2. 可以是冷冻期之后，今天买入的
- 有dp[i] [0]=max(dp[i-1] [0]，dp[i-1] [2]-prize[i])
对于dp[i] [1]
- 处于冷冻期，必定是之前持有股票后卖出后转换的状态
- dp[i] [1]=dp[i-1] [0]+prices[i])
对于dp[i] [2]
1. 可以是卖出后不在冷冻期内，没有处理，还是当天的状态
2. 可以是卖出后处于冷冻期，今天转入非冷冻期
- dp[i] [2]=max(dp[i-1] [2]，dp[i-1] [1])
之后，我们取三种情况的最大值即可
但是dp[n-1] [0]也就是最后一天买入，之后又不能卖，肯定是不合理的，所以我们最后只比较后两个状态即可

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==1){
            return 0;
        }
        //dp 表示天结束后的最大收益
        int [][]dp=new int[prices.length][3];
        dp[0][0]=-prices[0];//手里持有股票的收益,当天买入
        dp[0][1]=0;//手里不持有股票，且结束后在冷冻期，当天卖出
        dp[0][2]=0;//手里不持有股票，且结束后不在冷冻期，冷冻期之后
        for (int i = 1; i <dp.length ; i++) {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1]=dp[i-1][0]+prices[i];
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]);

        }
        return Math.max(dp[prices.length-1][1],dp[prices.length-1][2]);
    }
}