Best Time to Buy and Sell Stock I

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

``````

class Solution {
public:
int maxProfit(vector&amp;amp;amp;amp;amp;lt;int&amp;amp;amp;amp;amp;gt;&amp;amp;amp;amp;amp;amp; prices) {
if(prices.size() &amp;amp;amp;amp;amp;lt; 2) return 0;
int max = 0;
int maxSell = prices[prices.size() - 1];

for(int i = prices.size() - 1; i &amp;amp;amp;amp;amp;gt;= 1; --i)
{
if(prices[i] &amp;amp;amp;amp;amp;lt; maxSell || prices[i] &amp;amp;amp;amp;amp;lt;= 0) continue;
if(i &amp;amp;amp;amp;amp;gt; 0) minBuy = prices[i - 1];

for(int j = i - 1; j &amp;amp;amp;amp;amp;gt;= 0; --j)
{
if(prices[j] &amp;amp;amp;amp;amp;gt;= prices[i]) continue;
if(prices[i] - prices[j] &amp;amp;amp;amp;amp;gt; max) max = prices[i] - prices[j];
}
}
return max;
}
};
396ms
``````

Solution 2

``````
class Solution {
public:
int maxRes = 0, minPrice = 0;
int max(int a, int b){ return a &amp;amp;gt; b ? a : b; }
int maxProfit(vector&amp;amp;lt;int&amp;amp;gt;&amp;amp;amp; prices) {
int size = prices.size();
if(size &amp;amp;lt; 2) return 0;

minPrice = prices[0];
for(int i = 1; i &amp;amp;lt; size; ++i)
{
if(prices[i] &amp;amp;lt; minPrice) { minPrice = prices[i]; continue; }
maxRes = max(maxRes, prices[i] - minPrice);
}
return maxRes;
}
};
8ms
``````

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution

``````
class Solution {
public:
int maxProfit(vector&lt;int&gt;&amp; prices) {
prices.push_back(0);//补0作为结束符
int res = 0, ptr = 0, small = 0;

while(ptr &lt; prices.size() - 1)
{
while(ptr &lt; prices.size() - 1 &amp;&amp; prices[ptr] &gt; prices[ptr + 1]) ++ptr;
small = prices[ptr];
while(ptr &lt; prices.size() - 1 &amp;&amp; prices[ptr] &lt;= prices[ptr + 1]) ++ptr;
res += prices[ptr] - small;
}
return res;
}
};
8ms
``````

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

1.对于前半部分而言，由于是每次增加一个元素求此部分最大值是否变化，所以和I的做法一模一样，只要用一个DP数存之前的最大profit，用一个smallest存此区域内最小数，然后每次检查下新的元素增加进来是否会增大profit，如果增大就更新max profit。maxProfit = max{ maxProfit, prices[i] – smallest }
2.后半部分稍微有些麻烦，因为是每次删除一个元素所以不能简单通过前半部分的方法判断该区域内最大profit的变化情况。通过观察发现并不是每次删除元素就一定需要重新计算该部分的最大profit，而是当删除的是得到最大profit买入值（e.g.假设后半部分为{3,5,1,6,8}，那么得到的最大profit是7，买入值为1）时才会需要重新计算后半部的最大profit。所以当我们每次重新计算时，要记录该买入值的index，只有当遍历到该index的时候才重新计算后半部分。这里要注意可能后半部分profit为0，也就是后半部分array中的值都是降序排列的，这样要将index直接放到array末尾处也就是ArraySize处，因为这种情况下永远没必要更新后半部分最大profit。
Solution

``````
class Solution {
public:
int sectionMax(vector<int>& prices, int s, int f, int &secSmallIndex)
{
if(f - s < 1) { secSmallIndex = prices.size(); return 0; }
int res = 0, smallest = prices[s];
int tempSmallIndex = s;

for(int i = s; i <= f; ++i)
{
if(prices[i] < smallest) { smallest = prices[i]; tempSmallIndex = i; continue; }
if(prices[i] - smallest > res) { res = prices[i] - smallest; secSmallIndex =                     tempSmallIndex; }
}
if(res == 0) secSmallIndex = prices.size();
return res;
}

int maxProfit(vector<int>& prices) {
if(prices.size() < 1) return 0;
int maxRes = 0, firstMax = 0, secondMax = 0;
int firstSecSmall = prices[0], secondSecSmallIndex = 0;
maxRes = secondMax = sectionMax(prices, 0, prices.size() - 1,       secondSecSmallIndex);
for(int i = 0; i < prices.size(); ++i)
{
if(prices[i] < firstSecSmall) firstSecSmall = prices[i];
if(prices[i] - firstSecSmall > firstMax) firstMax = prices[i] - firstSecSmall;
if(i + 1 > secondSecSmallIndex)
secondMax = sectionMax(prices, i + 1, prices.size() - 1, secondSecSmallIndex);

maxRes = max(maxRes, firstMax + secondMax);
}
return maxRes;
}
};
8ms</pre>
<pre>``````