• <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>

            雁過無痕

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::

             

            思路:由于數組元素總和是固定值,因而跨頭、尾的連續子數組和最大,等價于求 中間那段和最小。因此,問題轉為計算 連續子數組的最大和 與 連續子數組的最小和


            import std.algorithm;

             

            int ring_max_continue_sum(in int[] src)

            {

             int min_sum = src[0], cur_min_sum = min_sum;

             int max_sum = src[0], cur_max_sum = max_sum;

             int total_sum = src[0];

             

             foreach (value; src[1 .. $]) {

                cur_min_sum = min(value, cur_min_sum + value);

                min_sum = min(min_sum, cur_min_sum);

              

                cur_max_sum = max(value, cur_max_sum + value);

                max_sum = max(max_sum, cur_max_sum);

              

                total_sum += value;

             }

             return max(max_sum, total_sum - min_sum);

            }

             

            unittest {

             auto ta = [3, -2, 3];

             auto tb = [3, 4, -2, 3, -7, 1, -3, 8];

             assert(ta.ring_max_continue_sum == 6);

             assert(tb.ring_max_continue_sum == 16);

            }

             

            void main()

            {

            }

             

            posted on 2011-07-20 23:49 flyinghearts 閱讀(2470) 評論(2)  編輯 收藏 引用 所屬分類: 算法 、編程之美

            評論

            # re: 對環狀數組求連續子數組的最大和[未登錄] 2012-05-20 00:57 galaxy
            如果數全為負,這種邊界情況有問題。  回復  更多評論
              

            # re: 對環狀數組求連續子數組的最大和 2012-05-20 19:28 flyinghearts
            @galaxy
            確實是。

            解決方法也很簡單:

            return max(max_sum, total_sum - min_sum);

            改為:

            if (max_sum < 0) return max_sum;
            return max(max_sum, total_sum - min_sum);

            或者改為:

            if (total_sum == min_sum) return max_sum;
            return max(max_sum, total_sum - min_sum);

              回復  更多評論
              

            国产亚洲美女精品久久久| 久久综合丁香激情久久| 婷婷久久五月天| 久久久久久国产精品免费无码| 久久精品国产网红主播| 99久久无码一区人妻| 国产精品美女久久福利网站| 91精品国产91久久久久福利| 久久久久亚洲AV无码专区网站| 久久婷婷五月综合97色一本一本| 精品无码久久久久久国产| 亚洲中文字幕无码久久2020| 国产叼嘿久久精品久久| 久久久久久夜精品精品免费啦 | 久久免费小视频| 精品久久久久久无码不卡| 久久久久亚洲av无码专区导航| 久久久久一级精品亚洲国产成人综合AV区 | avtt天堂网久久精品| 久久精品国产亚洲AV不卡| 久久精品免费全国观看国产| 超级碰久久免费公开视频| 久久综合给合久久狠狠狠97色69| 久久无码国产| 久久久久国产一级毛片高清板| 国产精品久久久久影院嫩草| 久久夜色精品国产噜噜麻豆| 偷偷做久久久久网站| 色狠狠久久综合网| 一本色综合久久| 久久中文字幕精品| 2020久久精品亚洲热综合一本| 一本一本久久a久久精品综合麻豆| 麻豆久久| 狠狠色噜噜色狠狠狠综合久久 | 丰满少妇人妻久久久久久4| 久久亚洲熟女cc98cm| 99精品久久精品一区二区| 亚洲国产精品成人AV无码久久综合影院| 久久国产成人午夜AV影院| 九九久久精品国产|