Best time to buy and sell stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Analysis:
The idea is very simple: buy the stock at a lower price and sell it at a higher price in the future.
The easiest way is try to sell the stock from the 2nd day to the last day, and get the highest profit. For each sell day, get the lowest price before and compute the profit. The algorithm contains two loop, one from the second day to the last, and one from the first day to the current sell day. The complexity is O(n^2).
A better way. How to reduce the complexity ? Similar idea as above but pre-compute the minimum value for each day, which means for each day, compute and store the minimum price of the previous days. In this step the complexity is O(n). Then scan all the days to get the max profit, total complexity is still O(n).
The source code: O(n^2)
class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int res = 0;
if (prices.size()>1){
vector<int>::iterator it1,it2;
for (it1 = prices.begin()+1;it1!=prices.end();it1++){
for (it2 = prices.begin();it2!=it1;it2++){
if ((*it1-*it2)>res) {
res = *it1-*it2;
}
}
}
}
return res;
}
};
The source code O(n):
class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int res = 0;
if (prices.size()>1){
vector<int>::iterator it1,it2;
vector<int> minv;
int min1=prices[0];
for (it1 = prices.begin()+1;it1!=prices.end();it1++){
if (*it1<min1) { min1 = *it1;}
minv.push_back(min1);
}
for (int i = 1; i<prices.size();i++){
if (prices[i]-minv[i-1]>res){res = prices[i]-minv[i-1];}
}
}
return res;
}
};
Hi Yu,
ReplyDeleteI have another solution might be helpful.
class Solution {
public:
int maxProfit(vector &prices) {
if(prices.empty()) {return 0;}
int low = prices[0];
int high = prices[0];
int res = 0;
for(int i=0; ires)
res = high-low;
low = prices[i];
high = prices[i];
}
if(prices[i]>high) {
high = prices[i];
}
}
if(high-low>res)
res = high - low;
return res;
}
};
Hi Yu,
ReplyDeleteYou actually don't require that vector(minv) to store the minimum elements. As we require to store the current minimum only, so I guess a simple integer variable would be enough. Here's my code which might be helpful.
class Solution {
public:
int maxProfit(vector &prices) {
if (prices.size() < 2)
return 0;
int mini = prices[0];
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] - mini > profit) {
profit = prices[i] - mini;
}
if (prices[i] < mini) {
mini = prices[i];
}
}
return (profit);
}
};
Below is my solution to pay my tribute to Yu Zhu (he has many great solutions that I can not ever come out).
ReplyDeleteBelow code is accepted by OJ.
int maxProfit(vector& prices) {
if(prices.empty()) return 0;
int lowPrice=prices[0];
int maxProfit=0;
for(int i=0; i prices[i])?prices[i]:lowPrice;
int profit = prices[i] - lowPrice;
maxProfit = (maxProfit > profit)?maxProfit:profit;
}
return maxProfit;
}