• <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 };
            久久99亚洲综合精品首页| 热RE99久久精品国产66热| 精品久久久久久无码中文字幕一区| 中文字幕无码久久精品青草| 亚洲日本va中文字幕久久| 色综合久久无码五十路人妻| 久久99毛片免费观看不卡| 国内精品免费久久影院| 99精品国产免费久久久久久下载| 久久超乳爆乳中文字幕| 国产成人久久久精品二区三区 | 99久久er这里只有精品18| 久久久久国产精品| 一本久久a久久精品亚洲| 国产成人久久久精品二区三区| 久久精品日日躁夜夜躁欧美| 97精品伊人久久大香线蕉app| 亚洲欧美日韩久久精品| 69久久精品无码一区二区| 国产成年无码久久久免费| 久久一本综合| 国产成人精品久久亚洲| 久久久久99精品成人片欧美| 午夜精品久久久久久久无码| 99精品久久精品| 久久99国产乱子伦精品免费| 色婷婷狠狠久久综合五月| 精品亚洲综合久久中文字幕| 狠狠色噜噜色狠狠狠综合久久| 久久久久无码中| 久久久WWW免费人成精品| 亚洲综合婷婷久久| 办公室久久精品| 久久无码国产| 亚洲中文字幕伊人久久无码| 久久久久亚洲?V成人无码| 久久激情五月丁香伊人| 久久久精品视频免费观看| 久久久久亚洲AV无码专区网站 | 一本色道久久综合狠狠躁篇| 国内精品久久久久久久久|