LeetCode 123. Best Time to Buy and Sell Stock III

Problem:

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

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Do it DP front and back.

public class Solution {
    int[] pre;
    int[] post;
    
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        pre = new int[prices.length];
        post = new int[prices.length];
        
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            pre[i] = prices[i] - min > pre[i-1] ? prices[i] - min : pre[i-1];
        }
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            if (prices[i] > max) max = prices[i];
            post[i] = max - prices[i] > post[i+1] ? max - prices[i] : post[i+1];
        }
        
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            int p = pre[i] + post[i];
            if (p > profit) profit = p;
        }
        return profit;
    }
}

71 thoughts on “LeetCode 123. Best Time to Buy and Sell Stock III”

  1. Today, while I was at work, my cousin stole my apple ipad and tested to see if it can survive a forty foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views. I know this is completely off topic but I had to share it with someone!

  2. 大部份曾經生育或經歷更年期的女性都會面臨私密深處及外觀鬆弛問題,不單會影響自信心和伴侶的親密體驗,更有機會造成容易積菌及尿滲等健康問題。全港首部 Venus Fiore閨密儀 RF射頻 私密緊緻療程 專門針對私密各處包括陰道、陰唇及陰阜的專用治療頭,全面改善鬆弛問題;每個治療頭均採用一次性即棄治療蓋,確保衛生。還有ATC自動控溫綜合系統,讓療程的治療溫度被有效監控,療程自然更安全、更有效達至預期效果。全港首部 Venus Fiore閨密儀 RF射頻 私密緊緻療程Venus Fiore集中為女性私密之處提供最到位的呵護,專注重整陰道健康、收緊鬆弛陰唇和改善陰阜肥大問題。關鍵在於Venus Concept的王牌─糅合多極射頻與磁力脈衝的(MP)2磁頻專利技術,發揮提升細胞活躍度、重塑同時增加膠原蛋白、刺激毛細血管新生等作用,達至調整陰道濕潤度、pH值的效果,更重要的是顯著改善陰道彈性,使其回復年輕狀態。

  3. I simply want to mention I’m very new to weblog and seriously enjoyed you’re website. Probably I’m planning to bookmark your site . You certainly have remarkable stories. Regards for revealing your blog site.

  4. Restylane乃一系列用於美顏的長效透明質酸產品。 Restylane療程能有效撫平皺紋、美化臉型輪廓及唇部,並可改善膚質及肌膚的彈性。Restylane透明質酸作用原理 Restylane透明質酸均以非動物來源的透明質酸作為原料,獨有的NASHA™專利技術研製而成。微量Restylane透明質酸凝膠到皮膚中,可以讓您的面部肌膚恢復豐盈飽滿。 Restylane透明質酸中的透明質酸與人體內的天然透明質酸十分相似,使用前無需進行皮膚測試,引起過敏反應的機率亦極低。

  5. After looking into a number of the articles on your web page, I truly like your way of writing a blog. I book-marked it to my bookmark webpage list and will be checking back in the near future. Please visit my website too and tell me what you think.

  6. Howdy, i read your blog occasionally and i own a similar one and i was just wondering if you get a lot of spam feedback? If so how do you stop it, any plugin or anything you can recommend? I get so much lately it’s driving me crazy so any support is very much appreciated.

  7. Amazing blog! Do you have any recommendations for aspiring writers? I’m hoping to start my own blog soon but I’m a little lost on everything. Would you suggest starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m totally overwhelmed .. Any tips? Kudos!

  8. Excellent blog! Do you have any hints for aspiring writers? I’m planning to start my own blog soon but I’m a little lost on everything. Would you recommend starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m totally confused .. Any tips? Kudos!

  9. Great blog! Do you have any helpful hints for aspiring writers? I’m planning to start my own website soon but I’m a little lost on everything. Would you recommend starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m completely confused .. Any recommendations? Thanks!

  10. Great blog! Do you have any recommendations for aspiring writers? I’m planning to start my own site soon but I’m a little lost on everything. Would you suggest starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m completely overwhelmed .. Any tips? Thanks a lot!

  11. Great blog! Do you have any tips and hints for aspiring writers? I’m planning to start my own blog soon but I’m a little lost on everything. Would you recommend starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m totally confused .. Any tips? Kudos!

  12. Amazing blog! Do you have any tips and hints for aspiring writers? I’m hoping to start my own website soon but I’m a little lost on everything. Would you recommend starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m completely overwhelmed .. Any recommendations? Thank you!

  13. Great blog! Do you have any tips and hints for aspiring writers? I’m hoping to start my own blog soon but I’m a little lost on everything. Would you suggest starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m completely overwhelmed .. Any suggestions? Kudos!

  14. Amazing blog! Do you have any helpful hints for aspiring writers? I’m planning to start my own blog soon but I’m a little lost on everything. Would you advise starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m totally overwhelmed .. Any tips? Thanks!

  15. Jordan 12 Gym Red 2018 http://www.jordan12gymred.us.com/
    Nike Outlet satore http://www.nikefactoryoutletstoreonline.com/
    Nike Outlet satore http://www.nikefactoryoutletstoreonline.us/
    Nike Outlet satore http://www.nikestores.us.com/
    retro jordan 33 http://www.jordan33.us/
    cheap jerseys http://www.cheapjerseysfromchina.us/
    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 2018 http://www.redjordan12.us/
    Yeezys http://www.yeezy.com.co/
    Yeezy Shoes http://www.yeezys.us.com/
    Yeezy Shoes http://www.yeezysupply.us.com/
    Yeezy Boost 350 http://www.yeezy-shoes.us.com/
    Yeezy Boost http://www.yeezy-boost350.com/
    Yeezy Boost http://www.yeezyboost350.us.com/
    Yeezy Blue Tint http://www.yeezybluetint.com/
    Yeezy 500 http://www.yeezy500utilityblack.com/
    Yeezy 500 http://www.yeezy500utilityblack.us/
    Nike VaporMax http://www.vapor-max.org.uk/
    Salomon Shoes http://www.salomon-shoes.org.uk/
    Salomon UK http://www.salomons.me.uk/
    Salomon Shoes http://www.salomonspeedcross4.org.uk/
    Off White Air Jordan 1 http://www.offwhitejordan1.com/
    Nike VaporMax http://www.nikevapormax.org.uk/
    Nike Element 87 http://www.nikereactelement87.us.com/
    React Element 87 http://www.nikereactelement87.us/
    Nike Vapormax Plus http://www.nikeplus.us/
    Nike Outlet http://www.nike–outlet.us/
    Nike Outlet Store http://www.nikeoutletstoreonlineshopping.us/
    Nike Outlet Store http://www.nikeoutletonlineshopping.us/
    Cheap Nike NBA Jerseys http://www.nikenbajerseys.us/
    Nike Air Max http://www.nikeairmax.us/
    Nike Air Max 2017 http://www.max2017.us/
    Jordan Shoes 2018 http://www.jordan-com.com/
    Jordan 11 Concord 2018 http://www.jordan11-concord.com/
    Cheap Yeezy Boost http://www.cs7boots1.com/
    Wholesale Cheap NBA Jerseys http://www.cheapnba-jerseys.us/
    Birkenstock Sandals http://www.birkenstocksandalsuk.me.uk/
    Basketball Jersey http://www.basketball-jersey.us/
    Balenciaga http://www.balenciaga.me.uk/
    Balenciaga UK http://www.balenciagauk.org.uk/
    Balenciaga http://www.balenciagatriples.org.uk/
    Balenciaga UK http://www.birkenstocks.me.uk/
    Balenciaga http://www.balenciagatrainers.org.uk/
    Nike Air Max 270 http://www.airmax270.org.uk/
    Yeezy http://www.adidasyeezyshoes.org.uk/
    Adidas Yeezy Shoes http://www.adidasyeezyshoes.org.uk/

  16. Having read this I thought it was extremely enlightening. I appreciate you spending some time and effort to put this article together. I once again find myself spending way too much time both reading and posting comments. But so what, it was still worth it!

  17. Attractive section of content. I simply stumbled upon your web site and in accession capital to assert that I get actually enjoyed account your blog posts. Anyway I’ll be subscribing in your feeds or even I fulfillment you access constantly fast.

Leave a Reply