LeetCode 121. Best Time to Buy and Sell Stock

Problem:

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.

Solution:

Simple DP. Save the current min.

public class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            max = prices[i] - min > max ? prices[i] - min : max;
        }
        return max;
    }
}

13 thoughts on “LeetCode 121. Best Time to Buy and Sell Stock”

  1. 當蛋白線埋入皮膚後,皮下組織會將蛋白線視為異物,啟動異物反應,因此刺激膠原蛋白生長,且可促進新陳代謝,更新老化肌膚,所以客戶在術後也會發覺膚質變得較透亮白皙。膠原蛋白提拉線像一個“磁力線”一樣,將埋入處附近的肌肉和脂肪固定在原處,不會往下墜,其後會吸引皮下組織往蛋白線集中部位移動,就會逐漸產生提拉的緊實效果。也被用於填充美容的微整形,蛋白線材就好比蓋房子的鋼骨支架,先埋入皮膚當作基底結構,然後再注入好比水泥的玻尿酸或自體脂肪,因為有吸附力不易擴散,就可穩定固定住填充物,讓立體支撐力效果更好。

  2. I was just searching for this info for some time. After six hours of continuous Googleing, finally I got it in your web site. I wonder what’s the lack of Google strategy that do not rank this type of informative sites in top of the list. Generally the top sites are full of garbage.

  3. 濃縮滲透乳,幫助真皮層即時再生,肌膚重煥新生,恢復年輕,再現透亮膚色、緊緻彈性配合美白保濕成份,有效截擊黑色素根源,令肌膚深度水潤剔透。

  4. 如何選對粉底色?有一個秘密你要知 Harpersbazaar HK 有時不是你的粉底液品質不好,效果不好只是因為你選錯了色。世界上所有事情都不是非黑即白,選粉底液也一樣,白和黑的皮膚都有分很多色號。但對於如何選對粉底色這個世紀難題如何解決?有一個秘密你不可不知!

  5. Jordan 12 Gym Red http://www.jordan12gymred.us.com/
    nike factory outlet store online http://www.nikefactoryoutletstoreonline.com/
    nike factory outlet store online http://www.nikefactoryoutletstoreonline.us/
    Nike Store http://www.nikestores.us.com/
    jordan 33 http://www.jordan33.us/
    cheap jerseys from china http://www.cheapjerseysfromchina.us/
    cheap custom nfl jerseys http://www.customnfljerseys.us/
    air jordan 11 concord http://www.jordan11concord.us.com/
    Jordan 12 Gym Red 2018 http://www.jordan12gymred.us/
    Jordan 12 Gym Red http://www.redjordan12.us/
    Yeezy http://www.yeezy.com.co/
    Yeezys http://www.yeezys.us.com/
    Yeezy http://www.yeezysupply.us.com/
    Yeezy Shoes http://www.yeezy-shoes.us.com/
    Yeezy Boost http://www.yeezy-boost350.com/
    Yeezy Boost 350 V2 http://www.yeezyboost350.us.com/
    Yeezy Shoes http://www.yeezybluetint.com/
    Yeezy 500 Utility Black http://www.yeezy500utilityblack.com/
    Adidas Yeezy 500 http://www.yeezy500utilityblack.us/
    Vapor Max http://www.vapor-max.org.uk/
    Salomon UK http://www.salomon-shoes.org.uk/
    Salomon Shoes http://www.salomons.me.uk/
    Salomon Speedcross 4 http://www.salomonspeedcross4.org.uk/
    Off White Air Jordan 1 http://www.offwhitejordan1.com/
    Vapor Max http://www.nikevapormax.org.uk/
    Nike React Element 87 http://www.nikereactelement87.us.com/
    Nike React Element 87 http://www.nikereactelement87.us/
    Nike Plus http://www.nikeplus.us/
    Nike Outlet http://www.nike–outlet.us/
    Nike Outlet Store http://www.nikeoutletstoreonlineshopping.us/
    Nike Outlet Store Online Shopping http://www.nikeoutletonlineshopping.us/
    Cheap Nike NBA Jerseys http://www.nikenbajerseys.us/
    Air Max Nike http://www.nikeairmax.us/
    Air Max 2017 http://www.max2017.us/
    Jordan Shoes http://www.jordan-com.com/
    Jordan 11 Concord 2018 http://www.jordan11-concord.com/
    Kanye West Yeezys Boost Shoes http://www.cs7boots1.com/
    Cheap NBA Jerseys http://www.cheapnba-jerseys.us/
    Birkenstock UK http://www.birkenstocksandalsuk.me.uk/
    NBA Jerseys http://www.basketball-jersey.us/
    Balenciaga http://www.balenciaga.me.uk/
    Balenciaga UK http://www.balenciagauk.org.uk/
    Balenciaga UK http://www.balenciagatriples.org.uk/
    Balenciaga http://www.birkenstocks.me.uk/
    Balenciaga Trainers http://www.balenciagatrainers.org.uk/
    Nike Air Max 270 http://www.airmax270.org.uk/
    Yeezy http://www.adidasyeezyshoes.org.uk/
    Yeezy Shoes http://www.adidasyeezyshoes.org.uk/

Leave a Reply