每日一题之力扣121题买卖股票 (动态规划)_购入股票力扣

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
1
2
3
4
5

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

作者：力扣 (LeetCode)
1
2
3
4
5
6
7
8
9
10
11

这道题，利用暴力也可以解决，不过时间复杂度是O(n2)，那么先把暴力的列出来把，如下代码。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = (int)prices.size(), ans = 0;
        for (int i = 0; i < n; ++i){
            for (int j = i + 1; j < n; ++j) {
                ans = max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

下面来看一下动态规划的解法，实际上本题的目标就是找，截止到i这个点之前最低的值，使用一个ans来储存当前点-之前的min值，用max来比较得出ans的最大值，也就是最大利润，先上代码。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
       if(prices.size()==0) return 0;
        int mins =prices[0];
        int dp[prices.size()];
        dp[0]=0;
        for(int i=1;i<prices.size();i++)
        {
            dp[i]=max(dp[i-1],prices[i]-mins);
            //重点在这里 利用dp数组来存储最大值就可
            mins=min(mins,prices[i]);
            //利用mins 来存储 从0 到i的最小值也就是买入值，那么prices[i]就是卖出值
            //要先算利润再更新mins 防止 最小值就是当前值
            //买入和卖出都成了当前值就不符合题意了
        }
        return dp[prices.size()-1];

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20