• <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 閱讀(558) 評論(0)  編輯 收藏 引用 所屬分類: C/C++
            国产农村妇女毛片精品久久| 精品综合久久久久久97| 99久久精品久久久久久清纯| 久久久久国产日韩精品网站| 人妻无码精品久久亚瑟影视| 久久久久久人妻无码| 欧洲国产伦久久久久久久| 97精品伊人久久久大香线蕉| 亚洲国产精品久久久久| 久久精品日日躁夜夜躁欧美| 九九99精品久久久久久| 伊人久久精品无码二区麻豆| 久久精品国产WWW456C0M| 国产麻豆精品久久一二三| 一本久久免费视频| 久久夜色精品国产www| 久久综合中文字幕| 好属妞这里只有精品久久| 久久精品一本到99热免费| 伊人久久大香线蕉AV一区二区| 丁香五月网久久综合| 人妻无码αv中文字幕久久| 亚洲精品无码久久久久AV麻豆| 久久国产精品免费一区二区三区 | 欧美色综合久久久久久| 久久天堂电影网| 亚洲狠狠综合久久| 亚洲综合婷婷久久| 久久亚洲精品视频| 国产91久久综合| 久久国产免费| 久久久久无码专区亚洲av| 99久久夜色精品国产网站| 久久国产成人午夜aⅴ影院 | 亚洲欧洲中文日韩久久AV乱码| 久久精品亚洲男人的天堂| 狠狠色伊人久久精品综合网 | 国产成人精品白浆久久69| 久久综合亚洲欧美成人| 精品熟女少妇a∨免费久久| 性欧美大战久久久久久久久 |