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.

由于只能一次买卖,所以最直接的想法是BF求出所有区间的profits,找出最大profit。(注意这里不是找最大最小值,因为买必须在卖之前)但这样会超时,所以需要用剪枝去掉buy price小于sell price的部分。算法复杂度O(n^2)。

Solution 1



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

                for(int i = prices.size() - 1; i >= 1; --i)
                {
                        if(prices[i] < maxSell || prices[i] <= 0) continue;
                        if(i > 0) minBuy = prices[i - 1];

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

仔细考虑发现其实有很多次的重复运算,所以用一个DP数maxProfit来储存到第i个stock为止的最大profit,再用一个smallest数存储到第i个stock为止的最小stock,由此得出递推公式 maxProfit = max{ maxProfit, prices[i] – smallest }。此算法复杂度为O(n),空间复杂度O(1)。

Solution 2


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

                minPrice = prices[0];
                for(int i = 1; i < size; ++i)
                {
                        if(prices[i] < 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).

这个题其实就是求最长增序子序列,因为对任意子序列来说其中最长增序子序列中最大和最小值差值的和为最大值。证明:设递增序列a,b,c,d, 其中a < b, b < c, c < d, 则d – a > (b – a) + (d – c) = (d – a) + (b – c), 若此时增加e使得e小于d,则e – a < d – a,若后接递增序列e,f,g,h (此时为a,b,c,d,e,f,g,h),则h – a < (h – e) + (d – a) = (h – a) + (d – e),由此递推到整个序列可知结论成立。算法时间复杂度O(n)。

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).

这个题是I的变种,但这次要求最多可以进行两次买卖,也就是说可以一次也可以两次(注意不一定两次买卖就能获得最大profit,e.g. {1,2,3,4})。
由于两次买卖所以可以看作是将array分成两部分,每个部分取其中最大profit再求和,我们要做的是找到这个最大的和。所以我们从0开始到ArraySize-1为止,遍历所有的两部分和的状况。
现在的问题是如何高效求得每种情况下的两部分和:(暴力重复使用I中的方法会造成TLE)
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>

Leave a Reply

Your email address will not be published. Required fields are marked *