动态规划之买卖股票的最佳时机——Leecode

浅浅的花香味﹌ 2022-05-11 10:20 175阅读 0赞

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

[https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/description/][https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock_description]

> 给定一个数组，它的第 *i* 个元素是一支给定股票第 *i* 天的价格。
> 
> 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

**示例 1:**

>     输入: [7,1,5,3,6,4]
>     输出: 5
>     解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
>          注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

**示例 2:**

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

**代码实现：**

//方法一
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int b1=INT_MIN;
            int s1=0;
            for(int i=0;i<prices.size();i++)
            {
                b1=max(b1,-prices[i]);
                s1=max(s1,b1+prices[i]);
            }
            return s1;
        }
    };
    
    
    //方法二
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if (prices.size()<1)
                return 0;
           int res=0;
           int m = prices[0];//买入最小值
           for(int i=1;i<prices.size();i++)
           {
               res=max(res,prices[i]-m);
               m=min(prices[i],m);
           }
           return res;
        }
    };

### **2.题目** ：买卖股票的最佳时机 II ###

[https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/][https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock-ii_description]

> 给定一个数组，它的第 *i* 个元素是一支给定股票第 *i* 天的价格。
> 
> 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

**示例 1:**

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

**示例 2:**

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

**示例 3:**

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

**原理：**

> 只要把所有的连续上升子串的的两个端点找到就好了

**代码实现：**

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.empty())  //判断输入是否为空
                return 0;
    
            //贪心算法
            int maxPro = 0,temp = 0;//最大收益、差值
            for(int i=1;i<prices.size();i++)//判断所有上升的值
            {   
                temp = prices[i]-prices[i-1];
                if(temp>0)
                    maxPro +=temp; 
            }
            return maxPro;  
        }
    };

### 3.题目：买卖股票的最佳时机 III ###

[https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/description/][https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock-iii_description]

> 给定一个数组，它的第* i* 个元素是一支给定的股票在第 *i *天的价格。
> 
> 设计一个算法来计算你所能获取的最大利润。你最多可以完成 *两笔 *交易。

**注意:** 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

**示例 1:**

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

**示例 2:**

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

**示例 3:**

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

**原理：**

> **确保每次剩下的钱最多**
> 
> <table style="width:500px;"> 
>  <tbody> 
>   <tr> 
>    <td>&nbsp;</td> 
>    <td>7</td> 
>    <td>1</td> 
>    <td>5</td> 
>    <td>3</td> 
>    <td>6</td> 
>    <td>4</td> 
>   </tr> 
>   <tr> 
>    <td>第一次买入</td> 
>    <td>-7</td> 
>    <td>-1</td> 
>    <td>-1</td> 
>    <td>-1</td> 
>    <td>-1</td> 
>    <td>-1</td> 
>   </tr> 
>   <tr> 
>    <td>第一次卖出</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>4</td> 
>    <td>4</td> 
>    <td>5</td> 
>    <td>5</td> 
>   </tr> 
>   <tr> 
>    <td>第二次买入</td> 
>    <td>-7</td> 
>    <td>-1</td> 
>    <td>-1</td> 
>    <td>1</td> 
>    <td>1</td> 
>    <td>1</td> 
>   </tr> 
>   <tr> 
>    <td>第二次卖出</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>4</td> 
>    <td>4</td> 
>    <td>7</td> 
>    <td>7</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> <table style="width:500px;"> 
>  <tbody> 
>   <tr> 
>    <td>&nbsp;</td> 
>    <td>3</td> 
>    <td>3</td> 
>    <td>5</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>3</td> 
>    <td>1</td> 
>    <td>4</td> 
>   </tr> 
>   <tr> 
>    <td>第一次买入</td> 
>    <td>-3</td> 
>    <td>-3</td> 
>    <td>-3</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>0</td> 
>   </tr> 
>   <tr> 
>    <td>第一次卖出</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>2</td> 
>    <td>2</td> 
>    <td>2</td> 
>    <td>3</td> 
>    <td>3</td> 
>    <td>4</td> 
>   </tr> 
>   <tr> 
>    <td>第二次买入</td> 
>    <td>-3</td> 
>    <td>-3</td> 
>    <td>-3</td> 
>    <td>2</td> 
>    <td>2</td> 
>    <td>2</td> 
>    <td>2</td> 
>    <td>2</td> 
>   </tr> 
>   <tr> 
>    <td>第二次卖出</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>2</td> 
>    <td>2</td> 
>    <td>2</td> 
>    <td>5</td> 
>    <td>5</td> 
>    <td>6</td> 
>   </tr> 
>  </tbody> 
> </table>

**代码实现：**

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int b1=INT_MIN,b2=INT_MIN;//买入的初始值为int的下界，-2^31-1
            int s1=0,s2=0;        //卖出初始化为0
            for(int i=0;i<prices.size();i++)
            {
                b1=max(b1,-prices[i]);
                s1=max(s1,b1+prices[i]);
                b2=max(b2,s1-prices[i]);
                s2=max(s2,b2+prices[i]);
            }
            return s2;
        }
    };

### **题目4：**买卖股票的最佳时机 IV ###

[https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/description/][https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock-iv_description]

> 给定一个数组，它的第* i* 个元素是一支给定的股票在第 *i *天的价格。
> 
> 设计一个算法来计算你所能获取的最大利润。你最多可以完成 **k** 笔交易。

**注意:** 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

**示例 1:**

>     输入: [2,4,1], k = 2
>     输出: 2
>     解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

**示例 2:**

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

**原理：**

> 注意：当交易次数大于天数，看作是贪心算法

**代码实现：**

class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if(k > prices.size())//当交易次数大于天数，看作是贪心算法
            {
                int res = 0;
                for(int i = 1 ; i < prices.size(); i++) if(prices[i] > prices[i-1]) res += prices[i]-prices[i-1];
                return res;
            }
    
            vector<int> sell(k+1, 0), buy(k+1, INT_MIN);//第n次的卖出、买入的数组
            for(int i = 0; i < prices.size() ; i++)
            {
                for(int  j = k; j > 0 ; j--)        //交易次数,从后面倒过来
                {
                    sell[j] = max(sell[j], buy[j] + prices[i]);
                    buy[j] = max(buy[j], sell[j-1] - prices[i]);
                }
            }
            return sell[k];
        }
    };

[https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock_description]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/description/
[https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock-ii_description]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/
[https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock-iii_description]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/description/
[https_leetcode-cn.com_problems_best-time-to-buy-and-sell-stock-iv_description]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/description/