题目内容
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
1
2
3
4
| 输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
|
示例 2:
1
2
3
| 输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
|
解法一：依次遍历
思路：寻找最低价格和最高价格
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<=1)return 0;
int in = prices[0];
int res = 0;
for(int price:prices){
in = min(in,price);
res = max(price-in,res);
}
return res > 0 ? res : 0;
}
};
|
结果：
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
0 ms
, 在所有 C++ 提交中击败了
100.00%
的用户
内存消耗：
12.6 MB
, 在所有 C++ 提交中击败了
13.89%
的用户
通过测试用例：
200 / 200
|
解法二：动态规划
思路:dp[i] = max(dp[i-1],prices[i] - min(prices[0]…prices[i]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<=1)return 0;
vector<int> dp(prices.size());
// dp[i] = max(dp[i-1],prices[i] - min(prices[0]...prices[i]))
int in = prices[0];
dp[0] = 0;
for(int i=01;i<dp.size();i++){
in = min(in,prices[i]);
dp[i] = max(dp[i-1],prices[i] - in);
}
return dp[dp.size()-1];
}
};
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
4 ms
, 在所有 C++ 提交中击败了
88.62%
的用户
内存消耗：
12.7 MB
, 在所有 C++ 提交中击败了
9.50%
的用户
通过测试用例：
200 / 200
|
优化一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<=1)return 0;
int in = prices[0];
int l = 0,r = 0;
for(int i=01;i<prices.size();i++){
in = min(in,prices[i]);
r = max(l,prices[i] - in);
l = r;
}
return l;
}
};
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
4 ms
, 在所有 C++ 提交中击败了
88.62%
的用户
内存消耗：
12.3 MB
, 在所有 C++ 提交中击败了
98.50%
的用户
通过测试用例：
200 / 200
|
