• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594
            Best Time to Buy and Sell Stock
            給出n天中每天的股票市值,選定合適的時間買進和賣出一次,問最多賺多少
            一開始想都沒想O(n^2)暴力一次,果然TLE
            然后想到股票市值按日期兩兩相減,然后就是求最大子段和的問題了。。下面兩種寫法這題都ok,但做Maximum Subarray這題的時候發現第二種寫法是錯的,因為存在數列全負的情況!

            Maximum Subarray
            裸的求最大子段和的問題,跟上題一樣。。
             1 class Solution {
             2 public:
             3     int maxProfit(vector<int> &prices) {
             4         int profit[100010], dp[100010], mx = 0, tp = 0, n = prices.size();
             5         for(int i = 0; i < n - 1; ++i) {
             6             profit[i + 1] = prices[i + 1] - prices[i];
             7         }
             8         dp[0] = 0;
             9         for(int i = 1; i < n; ++i) {
            10             tp += profit[i];
            11             if(tp > mx) {
            12                 mx = tp;
            13                 dp[i] = mx;
            14             }
            15             else
            16                 dp[i] = dp[i - 1];
            17             if(tp < 0) tp = 0;
            18         }
            19         return mx;
            20     }
            21 };

             1 class Solution {
             2 public:
             3     int maxProfit(vector<int> &prices) {
             4         int profit[100010], dp[100010], mx = 0, n = prices.size();
             5         for(int i = 0; i < n - 1; ++i) {
             6             profit[i + 1] = prices[i + 1] - prices[i];
             7         }
             8         dp[0] = 0;
             9         for(int i = 1; i < n; ++i) {
            10             if(dp[i - 1] + profit[i] < 0) dp[i] = 0;
            11             else
            12                 dp[i] = dp[i - 1] + profit[i];
            13             if(dp[i] > mx) mx = dp[i];
            14         }
            15         return mx;
            16     }
            17 };
            久久偷看各类wc女厕嘘嘘| 九九99精品久久久久久| 精品久久久久中文字幕一区| 久久综合狠狠色综合伊人| 国内精品久久久久久久久电影网| 久久精品成人欧美大片| 亚洲人成无码网站久久99热国产| 久久这里有精品| 国产成人久久精品一区二区三区 | 99久久99这里只有免费的精品| 韩国无遮挡三级久久| 久久伊人精品青青草原日本| 国产69精品久久久久观看软件| 久久久久亚洲Av无码专| 国产视频久久| 久久99国产精品尤物| 久久99精品国产麻豆蜜芽| 久久WWW免费人成一看片| 伊人久久大香线蕉精品| 午夜人妻久久久久久久久| 久久国产香蕉视频| 国产成人精品久久二区二区| 久久精品国产亚洲av麻豆蜜芽| 国产精品免费看久久久香蕉| 久久国产精品99国产精| 97香蕉久久夜色精品国产| 国产高清美女一级a毛片久久w | 久久这里只有精品久久| 亚洲AV无码久久精品色欲 | 亚洲欧美日韩久久精品| 中文字幕成人精品久久不卡| 久久99精品久久久久子伦| 久久久久久久精品妇女99| 日韩十八禁一区二区久久| 国产精品99久久不卡| 狠狠色丁香婷婷久久综合不卡| 日韩人妻无码一区二区三区久久| 97精品伊人久久久大香线蕉 | 欧美精品久久久久久久自慰| 久久久久久久精品成人热色戒| 少妇久久久久久被弄到高潮|