求最大子序列之和

今天一下午在看sharepoint了，又有活干，所以时间比较紧凑，于是想起了前些日子写的求最大子序列之和，作为每日一小题吧，暂做自我安慰吧。

求最大子序列之和，主要要注意他的效率，

1，算法复杂度是O( pow( n, 2 ) )

int max_sub(int a[], int size)
{
	int i, j, v, max = a[0];

	for(int i = 0; i < size; i++)
	{
		v = 0;
		for(int j = i; j < size; j++)
		{
			v = v + a[j];
			if( v >  max)
			{
				max = v;
			}
		}
	}
	return max;
}

2，算法复杂度为o(n)

int max_sub2(int a[],int size)
{
	int i, max =0, temp_max =0;

	for(i = 0; i < size; i++)
	{
		temp_max = temp_max + a[i];
		if(temp_max > max)
			max = temp_max;
		else if(temp_max < 0)
			temp_max = 0;
	}
	return max;
}

3,还从网上看了一种递归的“分而治之”( divide-and-conquer )的方法。（现在转一下）

比如 4 -3 5 -2 -1 2 6 -2

First Second

把序列分为两部分，那么最长子序列要么在First，要么在Second，要么就既在First又在Second。

第一中情况只要求First的最大子序列（递归调用），第二中情况只要求Second的最大子序列（还是递归调用）。对于第三种情况，只要找到包含First最后一个元素（在例子中是2）在First的最大子序列（例子中是 4，-3，5，-2）和包含Second起始元素（-1）在Second的最大子序列（-1，2，6）然后相加就行了。

这种算法的复杂度计算和计算斐波那契数列的复杂度相似，设 N 个数的执行次数是 T( N ) ，那么 T( N ) = 2*T( N/2 ) + O( N ) 其中T( 1 ) = 1

O( N ) 可以看成 N ，那么可以观察得到 T( N ) = N * logN

int maxSumRec( const vector<int> & a, int left, int right ) {

    if ( left == right )

        if ( a[ left ] > 0 )

            return a[ left ];

        else 

            return 0;

 

    int center = ( left + right ) / 2;

    int maxLeftSum = maxSumRec( a, left, center );

    int maxRightSum = maxSumRec( a, center, right );

 

    int maxLeftBorderSum = 0, leftBorderSum = 0;

    for ( int i = center; i>= left; i-- ) {

        leftBorderSum += a[ j ];

        if ( leftBorderSum > maxLeftBorderSum )

            maxLeftBorderSum = leftBorderSum;

    }

 

    int maxRightBorderSum = 0, RightBorderSum = 0;

    for ( int i = center; i <= right; i++ ) {

        RightBorderSum += a[ j ];

        if ( RightBorderSum > maxRightBorderSum )

            maxRightBorderSum = rightBorderSum;

    }

 

    return max3( maxLeftSum, maxRightSum, maxLeftSum + maxRightSum );       //   判断三个数最大值的函数

}

 

int maxSubSum3( const vector<int> & a ) {

    return maxSumRec( a, 0, a.size() - 1 );

}