leetCode 121. Best Time to Buy and Sell Stock 數組

121. Best Time to Buy and Sell Stock

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:

Example 2:

題目大意：

在一個數組中，用後面的元素減去前面的元素得到最大值，傳回這個最大值。

思路：

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

采用記錄目前之前的最小值，用目前值減去之前最小的值獲得一個臨時最大值，周遊整個數組，找到最大值。

代碼如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>int</code> <code>maxProfit(vector&lt;</code><code>int</code><code>&gt;&amp; prices) {</code>

<code>        </code><code>if</code><code>(prices.size() &lt;= 1)</code>

<code>            </code><code>return</code> <code>0;</code>

<code>        </code><code>int</code> <code>max = 0;</code>

<code>        </code><code>int</code> <code>curMin = prices[0];</code>

<code>        </code> 

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = 1;i&lt;prices.size();i++)</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code><code>(prices[i] - curMin &gt; max)</code>

<code>                </code><code>max = prices[i] - curMin;</code>

<code>            </code><code>if</code><code>(prices[i] &lt; curMin)</code>

<code>                </code><code>curMin = prices[i];</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>max;</code>

<code>    </code><code>}</code>

<code>};</code>

<code></code>

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1837145