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

            huangyi5209

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              0 Posts :: 13 Stories :: 0 Comments :: 0 Trackbacks

            常用鏈接

            留言簿

            我參與的團隊

            搜索

            •  

            最新評論

            // win32console.cpp : 定義控制臺應用程序的入口點。
            //

            #include 
            "stdafx.h"
            #include 
            <iostream>
            #include 
            <vector>
            using namespace std;

            /* START: Fig02_05.txt */
            /**
            * Cubic maximum contiguous subsequence sum algorithm.
            */

            int maxSubSum1( const vector<int> & a )
            {
                
            /* 1*/      int maxSum = 0;

                
            /* 2*/      forint i = 0; i < a.size( ); i++ )
                
            /* 3*/          forint j = i; j < a.size( ); j++ )
                
            {
                    
            /* 4*/              int thisSum = 0;

                    
            /* 5*/              forint k = i; k <= j; k++ )
                    
            /* 6*/                  thisSum += a[ k ];

                    
            /* 7*/              if( thisSum > maxSum )
                    
            /* 8*/                  maxSum   = thisSum;
                }


                
            /* 9*/      return maxSum;
            }

            /* END */
            int test(vector<int> & a)
            {
                
            int sz = a.size();
                
            int maxN = 0;
                
            for (int i = 0; i < sz; i++)
                
            {
                    
            for (int j = i; j < sz; j++)
                    
            {
                        
            int thisN = 0;
                        
            for (int k = i; k <= j; k++)
                            thisN 
            += a[k];
             
                        
            if (thisN > maxN)
                            maxN 
            = thisN;
                    }

                }

                
            return maxN;
            }



            /* START: Fig02_06.txt */
            /**
            * Quadratic maximum contiguous subsequence sum algorithm.
            */

            int maxSubSum2( const vector<int> & a )
            {
                
            /* 1*/      int maxSum = 0;

                
            /* 2*/      forint i = 0; i < a.size( ); i++ )
                
            {
                    
            /* 3*/          int thisSum = 0;
                    
            /* 4*/          forint j = i; j < a.size( ); j++ )
                    
            {
                        
            /* 5*/              thisSum += a[ j ];

                        
            /* 6*/              if( thisSum > maxSum )
                        
            /* 7*/                  maxSum = thisSum;
                    }

                }


                
            /* 8*/      return maxSum;
            }

            /* END */

            /**
            * Return maximum of three integers.
            */

            int max3( int a, int b, int c )
            {
                
            return a > b ? a > c ? a : c : b > c ? b : c;
            }


            /* START: Fig02_07.txt */
            /**
            * Recursive maximum contiguous subsequence sum algorithm.
            * Finds maximum sum in subarray spanning a[left..right].
            * Does not attempt to maintain actual best sequence.
            */

            int maxSumRec( const vector<int> & a, int left, int right )
            {
                
            /* 1*/      if( left == right )  // Base case
                /* 2*/          if( a[ left ] > 0 )
                
            /* 3*/              return a[ left ];
                            
            else
                                
            /* 4*/              return 0;

                                
            /* 5*/      int center = ( left + right ) / 2;
                                
            /* 6*/      int maxLeftSum  = maxSumRec( a, left, center );
                                
            /* 7*/      int maxRightSum = maxSumRec( a, center + 1, right );

                                
            /* 8*/      int maxLeftBorderSum = 0, leftBorderSum = 0;
                                
            /* 9*/      forint i = center; i >= left; i-- )
                            
            {
                                
            /*10*/          leftBorderSum += a[ i ];
                                
            /*11*/          if( leftBorderSum > maxLeftBorderSum )
                                
            /*12*/              maxLeftBorderSum = leftBorderSum;
                            }


                            
            /*13*/      int maxRightBorderSum = 0, rightBorderSum = 0;
                            
            /*14*/      forint j = center + 1; j <= right; j++ )
                
            {
                    
            /*15*/          rightBorderSum += a[ j ];
                    
            /*16*/          if( rightBorderSum > maxRightBorderSum )
                    
            /*17*/              maxRightBorderSum = rightBorderSum;
                }


                
            /*18*/      return max3( maxLeftSum, maxRightSum,
                
            /*19*/                   maxLeftBorderSum + maxRightBorderSum );
            }


            /**
            * Driver for divide-and-conquer maximum contiguous
            * subsequence sum algorithm.
            */

            int maxSubSum3( const vector<int> & a )
            {
                
            return maxSumRec( a, 0, a.size( ) - 1 );
            }

            /* END */


            /* START: Fig02_08.txt */
            /**
            * Linear-time maximum contiguous subsequence sum algorithm.
            */

            int maxSubSum4( const vector<int> & a )
            {
                
            /* 1*/      int maxSum = 0, thisSum = 0;

                
            /* 2*/      forint j = 0; j < a.size( ); j++ )
                
            {
                    
            /* 3*/          thisSum += a[ j ];

                    
            /* 4*/          if( thisSum > maxSum )
                    
            /* 5*/              maxSum = thisSum;
                    
            /* 6*/          else if( thisSum < 0 )
                    
            /* 7*/              thisSum = 0;
                }


                
            /* 8*/      return maxSum;
            }

            /* END */

            /**
            * Simple test program.
            */


            int _tmain(int argc, _TCHAR* argv[])
            {
                vector
            <int> a( 8 );
                a[ 
            0 ] = 4; a[ 1 ] = -3; a[ 2 ] = 5; a[ 3 ] = -2;
                a[ 
            4 ] = -1; a[ 5 ] = 2; a[ 6 ] = 6; a[ 7 ] = -2;
                
            int maxSum;

                maxSum 
            = maxSubSum1( a );
                cout 
            << "Max sum is " <<  maxSum << endl;
                maxSum 
            = maxSubSum2( a );
                cout 
            << "Max sum is " <<  maxSum << endl;
                maxSum 
            = maxSubSum3( a );
                cout 
            << "Max sum is " <<  maxSum << endl;
                maxSum 
            = maxSubSum4( a );
                cout 
            << "Max sum is " <<  maxSum << endl;

                system(
            "pause");
                
            return 0;
            }


            posted on 2011-04-13 07:13 huangyi5209 閱讀(553) 評論(0)  編輯 收藏 引用 所屬分類: C/C++
            久久久WWW成人免费精品| 久久免费看黄a级毛片| 人妻丰满AV无码久久不卡| 亚洲国产成人精品女人久久久| 色综合合久久天天综合绕视看| 久久精品国产亚洲av麻豆色欲 | 成人资源影音先锋久久资源网| 久久久久久亚洲精品不卡 | 久久精品国产亚洲Aⅴ蜜臀色欲| 97精品久久天干天天天按摩| 久久er热视频在这里精品| 国产精品18久久久久久vr | 久久婷婷国产综合精品| 波多野结衣久久一区二区| 青青草原综合久久大伊人导航| 久久久久久国产a免费观看不卡| 亚洲精品视频久久久| 久久久久人妻一区二区三区| 无码人妻精品一区二区三区久久 | 久久亚洲国产中v天仙www | 一级做a爰片久久毛片人呢| 久久成人国产精品二三区| 91久久成人免费| 模特私拍国产精品久久| 无码人妻久久一区二区三区免费丨 | 亚洲欧美日韩久久精品| 中文字幕精品久久| 97久久国产综合精品女不卡 | 久久免费视频6| 久久这里的只有是精品23| 欧美精品九九99久久在观看| 熟妇人妻久久中文字幕| 国产综合成人久久大片91| 精品久久久久久国产| 国产福利电影一区二区三区,免费久久久久久久精 | 久久久久免费看成人影片| 国产激情久久久久影院| 中文字幕无码精品亚洲资源网久久| 亚洲伊人久久大香线蕉苏妲己| 国内精品久久久久影院薰衣草| 国产精品热久久毛片|