leetCode121.BestTimetoBuyandSellStock數(shù)組

121. Best Time to Buy and Sell Stock

10年積累的成都網(wǎng)站設(shè)計、做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有珠暉免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

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.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

題目大意：

在一個數(shù)組中，用后面的元素減去前面的元素得到最大值，返回這個最大值。

思路：

可以使用雙循環(huán)來出來，但是效率太低。沒有通過。

采用記錄當前之前的最小值，用當前值減去之前最小的值獲得一個臨時最大值，遍歷整個數(shù)組，找到最大值。

代碼如下：

class Solution {
public:
    int maxProfit(vector& prices) {
        if(prices.size() <= 1)
            return 0;
        int max = 0;
        int curMin = prices[0];
        
        for(int i = 1;i max)
                max = prices[i] - curMin;
            if(prices[i] < curMin)
                curMin = prices[i];
        }
        return max;
    }
};

2016-08-12 08:43:51

當前題目：leetCode121.BestTimetoBuyandSellStock數(shù)組
分享路徑：http://m.jiaotiyi.com/article/gccjed.html