Question :


Say you have an array for which the

i


th

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.


for example: array[]  = { 2, 5, 3, 8, 9, 4 } , maxProfit = 9 - 2 = 7.


Anwser 1 :

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(prices.size() == 0) return 0;
        
        int ret = 0;
        
        int len = prices.size();
        int maxPrice = prices[len-1];
        for(int i = len - 1; i >= 0; i--){
            maxPrice = max(prices[i], maxPrice);    // maxPrice
            ret = max(ret, maxPrice - prices[i]);   // maxProfit
        }
        
        return ret;
    }
};

注意点:

最大利润,应该是先买的最低价与后卖的最高价的差值,因此需要考虑时间先后顺序


Anwser 2 :

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int maxp = 0;
        int dp = 0;        
        for(int i = prices.size()-2; i >= 0 ;i--)
        {
            if(dp >= 0){
                dp += (prices[i+1] - prices[i]);
            } else {
                dp = max(0, prices[i+1] - prices[i]);
            }
            maxp = max(dp, maxp);
        }  
        return maxp;
    }
};

说明:

1) 此法把两数之间最大差,转化为了求两数组之间最大和

2) dp += (prices[i+1] - prices[i]) 实际上是 dp +=  (prices[i+1] - prices[i])  +  (prices[i] - prices[i-1])  +  (prices[i-1] - prices[i-2]) + ... =

(prices[i] - prices[j])

(i > j)



参考推荐:


数组中数对差最大