文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書
1. Description
Best Time to Buy and Sell Stock
2. Solution
- Version 1
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max_profit = 0;
for(int i = 0; i < prices.size(); i++) {
for(int j = i + 1; j < prices.size(); j++) {
int profit = prices[j] - prices[i];
if(profit > max_profit) {
max_profit = profit;
}
}
}
return max_profit;
}
};
- Version 2
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max = 0;
int min = INT_MAX;
vector<int> current_max(prices.size());
vector<int> current_min(prices.size());
int max_profit = 0;
int size = prices.size();
for(int i = 0; i < size; i++) {
if(prices[i] < min) {
min = prices[i];
}
current_min[i] = min;
}
for(int i = size - 1; i >= 0; i--) {
if(prices[i] > max) {
max = prices[i];
}
current_max[i] = max;
}
for(int i = 0; i < size; i++) {
int profit = current_max[i] - current_min[i];
if(profit > max_profit) {
max_profit = profit;
}
}
return max_profit;
}
};
- Version 3
class Solution {
public:
int maxProfit(vector<int>& prices) {
int min = INT_MAX;
int max_profit = 0;
for(int i = 0; i < prices.size(); i++) {
if(prices[i] < min) {
min = prices[i];
}
else if(prices[i] - min > max_profit) {
max_profit = prices[i] - min;
}
}
return max_profit;
}
};
