用二分法寻找最长连续单调递增子序列

/*在由n个数组成的序列中,找出最长的单调递增子序列。*/

#define DEBUG_MODE_

#ifdef DEBUG_MODE_

#include <iostream>

#endif  /* DEBUG_MODE_ */

template <typename T>
void ArrCopy (
              const T   arrSource[],
              int       beginPos,
              T *&      arrDestination,
              int       count
              )
{
    arrDestination = new T[count];
    int pos = 0;
    for ( int i = beginPos; i < beginPos+count; ++i )
    {
        arrDestination[pos++] = arrSource[i];
    }
}

template <typename T>
void PrintArr (
               const T     arr[],
               const int   size
               )
{
    for( int i = 0; i < size; ++i )
    {
        std::cout<<arr[i]<<" ";
    }
    std::cout<<std::endl;
}

template <typename T>
void GetMaxIncSubArr(
                     const T    arr[],
                     const int  size,
                     T *&       sub,
                     T &        subSize
                     )
{
    if ( size <= subSize )
    {
        return;
    }

    int tSize = 1;

    int p = size>>1;
    while( p+1<=size &&
        arr[p+1] > arr[p] )
    {
        tSize++;
        p++;
    }
    p = size>>1;
    while( p>0 &&
        arr[p-1] < arr[p] )
    {
        tSize++;
        p--;
    }

    if ( tSize > subSize )
    {
        subSize = tSize;
        ArrCopy<T>(arr, p, sub, subSize);
    }

    int * left;
    int leftSize = p;
    if ( leftSize > subSize )
    {
        ArrCopy<T>(arr, 0, left, leftSize);
    }
  

    int * right;
    int rightSize = size-p-subSize;
    if ( rightSize > subSize )
    {
        ArrCopy<T>(arr, p+subSize, right, rightSize);
    }

    if ( p > subSize )
    {
        GetMaxIncSubArr(left, leftSize, sub, subSize);
        delete left;
    }
    if(rightSize > subSize)
    {
        GetMaxIncSubArr(right, rightSize, sub, subSize);
        delete right;
    }
}

int main(int argc, char* argv[])
{
    #ifdef DEBUG_MODE_
    int arr[17] = {0,8,6,1,3,6,6,0,8,9,4,5,3,1};
    int size = 14;
    int * sub;
    int subSize = 0;
    GetMaxIncSubArr<int>(arr, size, sub, subSize);
    PrintArr<int>(sub,subSize);
    delete sub;
    std::cin>>size;
    #endif  /* DEBUG_MODE_ */

    return 0;
}

责任编辑 webmaster

相关链接