Description

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

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

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

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

Solution

A了题目之后，这一题思路就比较清晰了，相信各位看官稍动脑筋应该也能想到，或者看代码进行分析。

当然，特别要注意列表为空的情况（此时应返回0！）

python

1 class Solution(object): 2     def maxProfit(self, prices): 3         """ 4         :type prices: List[int] 5         :rtype: int 6         """ 7         if len(prices) == 0: 8             return 0 9 10         max_diff = 011         cur_diff = 012         buy_price = prices[0]13         for item in prices[1:]:14             if item < buy_price:15                 buy_price = item16                 cur_diff = 017             else:18                 cur_diff = item - buy_price19                 max_diff = max(max_diff, cur_diff)20 21         return max_diff

cpp

1 class Solution { 2 public: 3     int maxProfit(vector
      
       & prices) { 4         if (prices.size()==0) 5             return 0; 6  7         int buy_price = prices.at(0); 8         int max_diff = 0; 9         int cur_diff = 0;10         int temp = 0;11         for (size_t i=1; i
       
        < cur_diff ? cur_diff : max_diff);22             }23         }24 25         return max_diff;26     }27 };