1、问题分析

题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

这里为了简单，我分几种情况说明一下
1、如果前面一个节点的最大利润值，即 dp[i-1] == 0
说明前面的数都比他大，所以此时计算当前节点的最大利润值，
只需要考虑当前节点和前面一个节点即可。这里还是分两种情况：
a、当前节点大于前置节点，说明dp[i] = price[i] - prices[i - 1],
此时 dp[i-1] == 0。所以上式又等于 dp[i] = price[i] - (prices[i - 1]- dp[i - 1])
b、当前节点小于等于前置节点，这时直接使用最小值 0 即可，你完全可以当天买，当天卖。
2、如果前面一个节点的最大利润值，即dp[i-1] > 0 ( 注意这里的最大利润值不可能小于 0)。
说明前面有最小的一个节点比前置节点小，那具体小多少呢？就是小 dp[i-1],所以可以推断出最小的那个节点为：
min_node = price[i-1] - dp[i-1],由于前面有更小的节点，所以我们当前的最大利润肯定是减去前面最小的节点
即dp[i] = price[i] - (price[i-1] - dp[i-1])
我们考虑了所有的情况，我们发现 dp[i]的表达式是一样的，即都是：dp[i] = price[i] - (price[i-1] - dp[i-1])

  代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

2、问题解决

  笔者以C++方式解决。

方法一：

#include "iostream"using namespace std;#include "algorithm"
#include "vector"
#include "queue"
#include "set"
#include "map"
#include "cstring"
#include "stack"class Solution {
private:// 记录以 i 天卖出则最大利润是多少,即定义一个最大利润数组// 例如 dp[2] 表明 第 3 天，卖出，则最大利润是dp[2]vector<int> dp;
public:int maxProfit(vector<int> &prices) {// 边界条件 如果数组小于等于1，说明最大利润为 0if (prices.size() <= 1) {return 0;}// 初始化利润数组dp.resize(prices.size());dealChen(prices);int result = INT32_MIN;// 寻找最大利润数组中的 最大值for (int i = 0; i < dp.size(); ++i) {if (dp[i] > result) {result = dp[i];}}// 返回整个数组的最大利润return result;}/*** 处理最大利润数组* @param prices*/void dealChen(const vector<int> &prices) {// 遍历股票数组for (int i = 1; i < prices.size(); ++i) {/*** 这里为了简单，我分几种情况说明一下* 1、如果前面一个节点的最大利润值，即 dp[i-1] == 0* 说明前面的数都比他大，所以此时计算当前节点的最大利润值，* 只需要考虑当前节点和前面一个节点即可。这里还是分两种情况：*      a、当前节点大于前置节点，说明dp[i] = price[i] - prices[i - 1],*      此时 dp[i-1] == 0。所以上式又等于 dp[i] = price[i] - (prices[i - 1]- dp[i - 1])*      b、当前节点小于等于前置节点，这时直接使用最小值 0 即可，你完全可以当天买，当天卖。* 2、如果前面一个节点的最大利润值，即 dp[i-1] > 0 ( 注意这里的最大利润值不可能小于 0)。* 说明前面有最小的一个节点比前置节点小，那具体小多少呢？就是小 dp[i-1],所以可以推断出最小的那个节点为：* min_node = price[i-1] - dp[i-1],由于前面有更小的节点，所以我们当前的最大利润肯定是减去前面最小的节点* 即 dp[i] = price[i] - (price[i-1] - dp[i-1])** 我们考虑了所有的情况，我们发现 dp[i]的表达式是一样的，即都是：dp[i] = price[i] - (price[i-1] - dp[i-1])* 因此我们可以合二为一，写出下式*/dp[i] = prices[i] - (prices[i - 1] - dp[i - 1]);// 这里注意边界，即最小值的情况dp[i] = dp[i] > 0 ? dp[i] : 0;}}
};int main() {vector<int> prices = {7, 1, 5, 3, 6, 4};Solution *pSolution = new Solution;int i = pSolution->maxProfit(prices);cout << i << endl;system("pause");return 0;
}

方法二

#include "iostream"using namespace std;#include "algorithm"
#include "vector"
#include "queue"
#include "set"
#include "map"
#include "cstring"
#include "stack"class Solution {
public:/*** 其实前面的方法，我们可以压缩空间利用率* 对于公式 dp[i] = prices[i] - (prices[i - 1] - dp[i - 1]);* 我们发现 dp[i] ，dp[i-1] 都是用过即丢的数据，没有必要存储起来，* 之前只是为了方便理解才这么定义。* 这里我们完全可以进行优化，我们知道，计算的时候，我们只需要知道* dp[i-1]就行了，prices[i]等是数组给定的，不需要我们关心。* 所以我们完全可以使用一个变量来运算，* nowData = prices[i] - (prices[i - 1] - nowData);* 更新之后的 nowData 进入下一次迭代计算* 具体思路和上面的类似，只是优化了空间利用率* @param prices* @return*/int maxProfit(vector<int> &prices) {// 边界条件 如果数组小于等于1，说明最大利润为 0if (prices.size() <= 1) {return 0;}int nowData = 0;int max_result = 0;for (int i = 1; i < prices.size(); ++i) {nowData = prices[i] - (prices[i - 1] - nowData);nowData = nowData > 0 ? nowData : 0;if (max_result < nowData) {max_result = nowData;}}return max_result;}};int main() {vector<int> prices = {7, 1, 5, 3, 6, 4};Solution *pSolution = new Solution;int i = pSolution->maxProfit(prices);cout << i << endl;system("pause");return 0;
}

运行结果

有点菜，有时间再优化一下。

3、总结

  难得有时间刷一波LeetCode, 这次做一个系统的记录，等以后复习的时候可以有章可循，同时也期待各位读者给出的建议。算法真的是一个照妖镜，原来感觉自己也还行吧，但是算法分分钟教你做人。前人栽树，后人乘凉。在学习算法的过程中，看了前辈的成果，受益匪浅。
感谢各位前辈的辛勤付出，让我们少走了很多的弯路！
哪怕只有一个人从我的博客受益，我也知足了。
点个赞再走呗！欢迎留言哦！