题目描述:来自LeetCode
方法一：暴力解（会超时）
思路：遍历数组，从第二天开始只要满足条件，我们都可以选择卖出，?而买入的时间自然可以是卖出前的任意一天，所以用一个变量来保存最小值，在遍历的时候，外层循环遍历数组更新可以获得的最大利润，内层循环用来更新第i天卖出，哪一天买入可以获得的最大值。
代码实现c++:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxp=0;//保存第j天卖出可以获得的最大利润
int maxpr=0;//保存所有可以卖出的最大利润的最大利润
for(int i=0;i<prices.size();i++){
for(int j=i+1;j<prices.size();j++){
if(prices[j]-prices[i]>0){//当卖出大于买入的时候，我们更新，不然小于零收益为0
maxp=max(maxp,prices[j]-prices[i]);
}
maxpr=max(maxpr,maxp);//更新每一次卖出可以获得的最大值的最大值
}
}
return maxpr;
}
};方法二：动态规划
如何用O(N)的时间复杂度解决问题呢？ 遍历一趟数组，还是一样，遍历到任意一个我们都假设在这一天卖出，那要让这一天卖出能获得最大利润就是让买入时花的钱最少呗，所以我们就求这一天之前，哪一天买入花的最少，很简单，我们每次遍历的时候都更新一下数组从0到第i-1的最小值就行了，这个最小值就是目前位置买入花的钱最少的，让第i天卖出的钱减去这个最小，一定是第i天卖出收益最大的，然后我们求出这个最大之后，要跟之前求出来的收益比较，即更新最大利润中的最大利润。
代码实现C++:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minp=prices[0];//用来更新买入的最小值，从数组的第一个数开始
int maxp=0;//用来更新所有能卖出的最大利润的最大利润
for(int i=1;i<prices.size();i++){
maxp=max(maxp,prices[i]-minp);//更新这一天卖出所能获得的最大利润
minp=min(minp,prices[i]);//用来更新买入的最小值
}
return maxp;
}
};今日刷题任务完成啦~如有错误欢迎指正