LeetCode刷题笔记-动态规划-day7

柔情只为你懂 2023-10-01 18:12 1阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-动态规划-day7
 *   *  1014. 最佳观光组合
     *   *  1.题目
         *  2.解题思路
         *  3.代码
     *  121. 买卖股票的最佳时机
     *   *  1.题目
         *  2.解题思路
         *  3.代码
     *  122. 买卖股票的最佳时机 II
     *   *  1.题目
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-动态规划-day7 ##

### 1014. 最佳观光组合 ###

#### 1.题目 ####

> 原题链接：[1014. 最佳观光组合][1014.]

![image-20220211105613057][]

#### 2.解题思路 ####

1.  仔细观察`a[i] + a[j] + i - j`，可分解为：`(a[j]-j)+(a[i]+i)`
2.  又因为`i<j`，我们可以把`j`当做当前点，所以这道题我们只需要遍历一遍。用一个变量`f`维护`j`点之前的所有`a[i]+i`的最大值
3.  `res=max(res,f+a[j]-j);`扫描一遍即可求出最大值

#### 3.代码 ####

class Solution {
        
    public:
        int maxScoreSightseeingPair(vector<int>& a) {
        
            int f=a[0];
            int res=-1e9;
            for(int i=1;i<a.size();i++){
        
                res=max(res,f+a[i]-i);
                f=max(a[i]+i,f);
            }
            return res;
        }
    };

### 121. 买卖股票的最佳时机 ###

#### 1.题目 ####

> 原题链接：[121. 买卖股票的最佳时机][121.]

![image-20220211110208499][]

#### 2.解题思路 ####

1.  用一个变量`minn`维护`[0,i-1`\]的最小价格
2.  枚举到`i`时，`prices[i]-minn`就表示当前点`i`卖出的最大收益
3.  遍历所有点，取最大值：`res=max(res,prices[i]-minn);`

#### 3.代码 ####

class Solution {
        
    public:
        int maxProfit(vector<int>& prices) {
        
            int minn=1e9,res=0;
            for(int i=0;i<prices.size();i++){
        
                res=max(res,prices[i]-minn);
                minn=min(minn,prices[i]);
            }
            return res;
        }
    };

### 122. 买卖股票的最佳时机 II ###

#### 1.题目 ####

> 原题链接：[122. 买卖股票的最佳时机 II][122. _ II]

![image-20220211112425333][]

#### 2.解题思路 ####

算法：贪心

具体情况可以分为三类：

1.  单独交易日：设今天价格P1、明天价格P2，则今天买入、明天免除可赚取金额P2−P1(负值代表亏损)
2.  连续上涨交易日：设此上涨交易日股票价格分别为P1，P2，…，Pn 则第一天买最后一天卖收益最大，即Pn−P1；等价于每天都买卖，即Pn−P1=(P2−P1)+(P3−P2)+…+(Pn−Pn−1)
3.  连续下降交易日：则不买卖收益最大，即不会亏钱

总结可得到：由于不考虑交易次数。我们考虑相邻两天的股票价格，如果后一天的股票价格大于前一天的，那么在进行买入卖出操作后，即可获利。这样的贪心一定能获得最大的利润。

直接遍历整个数组。如果`prices[i+1]-prices[i]`大于0，则加入最终总利润。

#### 3.代码 ####

class Solution {
        
    public:
        int maxProfit(vector<int>& prices) {
        
            int res=0;
            for(int i=0;i<prices.size()-1;i++){
        
                res+=max(0,prices[i+1]-prices[i]);
            }
            return res;
        }
    };

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[1014.]: https://leetcode-cn.com/problems/best-sightseeing-pair/
[image-20220211105613057]: https://img-blog.csdnimg.cn/img_convert/918153d9ea13a6e4376258fd75e806ed.png
[121.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[image-20220211110208499]: https://img-blog.csdnimg.cn/img_convert/c8bc2a5f153c8c8a0be5767eefb01a40.png
[122. _ II]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
[image-20220211112425333]: https://img-blog.csdnimg.cn/img_convert/3b2b1da18387facc6237b8cb67dfa66b.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/e69a33f95d0045b8abfa01d68e36610e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16