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.
-------------------------------------------------
Solution #1 O(n^2) straight forward iteration.
class Solution {
public:
void profit (vector<int> &prices, vector<int> &prf, int index) {
int cur = prices[index];
int max = 0;
for (int i=index+1;i<prices.size();i++) {
int dif = prices[i] - cur;
if (dif > max) {
max = dif;
}
}
prf[index] = max;
if (index + 1 < prices.size())
profit(prices,prf,index+1);
}
int findMax (vector<int> &prf) {
int max = 0;
for (int i=0;i<prf.size();i++) {
if (prf[i]>max) max = prf[i];
}
return max;
}
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (prices.size() == 0) return 0;
vector<int> prf(prices.size());
profit(prices,prf,0);
return findMax(prf);
}
};
Solution #2 O(n)
Note: tracking the index of minimum value
class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int buy=0,sell=0;
int min=0;
int maxDif = 0;
for (int i=0;i<prices.size();i++) {
if (prices[min] > prices[i]) {
min = i;
}
int dif = prices[i] - prices[min];
if (dif > maxDif) {
buy = min;
sell = i;
maxDif = dif;
}
}
return maxDif;
}
};
Solution #3 O(n) space and efficiencyDP: max = prices[i] - prices[i-1] + prices[i-1] - prices[i-2] + .... + prices[j+1] - prices[j] = prices[i]- prices[j]
class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = prices.size();
if (size < 2) {
return 0;
}
int max = 0;
int curMax = 0;
for (int i=1;i<size;i++) {
if (curMax > 0) {
curMax += prices[i] - prices[i-1];
}else {
curMax = prices[i] - prices[i-1];
}
if (curMax > max) {
max = curMax;
}
}
return max;
}
};
Update - 1, Dec 27th 2013 Solution #4, a much easier DP approach
dp[i] represents the maximum profit among all prices, starting at index 0 to i. Hence dp[prices.size() - 1] has the max value we are looking for.
class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.size() == 0) return 0;
vector<int> dp(prices.size(),0);
int minimum = prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i] = max(dp[i - 1], prices[i] - minimum);
minimum = mim(prices[i],minimum);
}
return dp[prices.size() - 1];
}
};
Update - 2, Mar 29th 2014 Optimized space of Solution #4
class Solution {
public:
int maxProfit(vector<int> &prices) {
int size = prices.size();
if (size == 0) {
return 0;
}
int minimum = prices[0];
int maxP = 0;
for (int i = 0; i < size; i++) {
maxP = max (maxP, prices[i] - minimum);
minimum = min(minimum,prices[i]);
}
return maxP;
}
};
Solution #5, similar to #4. DP. thanks to Lan Xudp[i] has the highest price from dp[i + 1] to end
class Solution {
public:
int maxProfit(vector<int> &prices) {
int size = prices.size();
if (size == 0) {
return 0;
}
vector<int> dp(size,0);
for (int i = size - 2; i >= 0; i--) {
dp[i] = max(dp[i + 1], prices[i + 1]);
}
int maxP = 0;
for (int i = 0; i < size; i++) {
maxP = max(maxP, dp[i] - prices[i]);
}
return maxP;
}
};
Optimized space
class Solution {
public:
int maxProfit(vector<int> &prices) {
int size = prices.size();
if (size == 0) {
return 0;
}
int maxP = 0;
int highest = prices[size - 1]; // highest value from i to end
for (int i = size - 2; i >= 0; i--) {
maxP = max(maxP, highest - prices[i]);
highest = max(highest, prices[i]);
}
return maxP;
}
};
