精选50题之 122. 买卖股票的最佳时机 II

- 日理万妓 2024-04-19 11:55 42阅读 0赞

### 腾讯精选练习（50 题）之 122. 买卖股票的最佳时机 II ###

*   *  原题目链接
     *  直接实现
     *  其他实现

## 原题目链接 ##

给定一个数组，它的第 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 max_profit = 0;
            for (int i = 1; i < prices.size(); i++) {
        
                if (prices[i] > prices[i - 1])
                    max_profit += prices[i] - prices[i - 1];
            }
            return max_profit;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(1)

## 其他实现 ##

动态规划什么的?

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0e2da530e9594ad2b295af6dea298482.png