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

标签：出售 int 一天 II 122 最佳时机 result ans prices

题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回 你能获得的 最大利润 。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii

该问题可以用两种方法进行解答：

1.动态规划

　　每次遍历假设第 i 天为最后一天，那么对于最后一天而言，有两种情况：

1. 价格 > 前一天出售价格，那么前天出售时间推迟到第 i 天（赚更多钱嘛），所以利润为上一次利润 + price[i]-price[i-1]
2. 价格 <= 上一次出售价格，那么就直接出售咯.不然买进来就亏本了

　　 其实就是记录每一天作为最后一天的最大利润

　　本质上就是记录每一个连续的最大增区间，所有连续增区间的和就是问题的解

 1 class Solution {
 2 public:
 3     //记录前一天的最高
 4     //动态规划：
 5     //分解:每一个作为最后一天加入，那么影响的就是最后一个解
 6     int maxProfit(vector<int>& prices) {
 7         int N = prices.size();
 8         vector<int>result(N);
 9         result[0] = 0;
10         for (int i = 1; i < N; ++i)
11         {
12             if (prices[i] > prices[i-1])
13                 result[i] = result[i-1] + prices[i] - prices[i-1];
14             else
15                 result[i] = result[i-1];
16         }
17         return result[N - 1];
18     }
19 };

 2.贪婪算法

　　贪婪的思想就是能赚钱，我就买卖。这里可以理解为我当天卖出去，欸！我还能买进来，所以...(炒股吧家人们）

• 只要有增，我每天都能赚钱
• 不能增，我也不亏本

 1 class Solution {
 2 public: 4     
 6     int maxProfit(vector<int>& prices) {
 7         //贪婪算法求解
 8         int ans = 0, N = prices.size();
 9         for (int i = 1; i < N; ++i)
10         {
11             ans += max(0, prices[i] - prices[i - 1]);
12         }
13         return ans;
14     }
15 };

这里其实将问题转换为了当天卖当天买的问题，实际上也是如此。

 

标签：出售,int,一天,II,122,最佳时机,result,ans,prices
From： https://www.cnblogs.com/Kellen-Gram/p/17391928.html