算法1
暴力搜索
时间复杂度:O(n^2)
代码:打败 5%
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for (int i = 0; i < prices.size(); i ++)
for (int j = i; j < prices.size(); j ++ )
{
if (prices[i] <= prices[j])
{
profit = max(prices[j]-prices[i], profit);
}
else continue;
}
return profit;
}
};
算法2
(动态规划) O(n)
- 定义res, 定义min.
- 一层循环:每次循环更新res和min,
res = max(price[i] - min, res); min = min(price[i], min);
时间复杂度:O(n)
代码: 打败 66%
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0, min_price = INT_MAX;
for (int i = 0; i < prices.size(); i ++ )
{
min_price = min(prices[i], min_price);
res = max(prices[i]-min_price, res);
}
return res;
}
};
python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
min_price = float("inf")
res = 0
for i in range(n):
min_price = min(prices[i], min_price)
res = max(prices[i] - min_price, res)
return res