我写故我在

I write, therefore I am

程序员面试题集003

Posted by ieipi 于 九月 14, 2011

题目

在O(n)的时间内求出一个输入数组的最大子段和

思路一

最笨的方法就是遍历.遍历所有的子数组,并比较它们的和,获得最大者.
但时间复杂度为O(n^3).
源代码

int MaxSubSum1(const int arr[], int len)
{
    //there is at least one positive value in the input array.
    int MaxSum = 0;

    for ( int i=0; i<len; i++) {
        //start index of the subsequence.
        for ( int j=i; j<len; j++){
            //end index of the subsequence.
            int SubSum = 0;
            //caculate the sum of the subsequence.
            for ( int k=i; k<=j; k++) {
                SubSum += arr[k];
            }
            if(SubSum > MaxSum)
                MaxSum = SubSum;
        }
    }
    return MaxSum;
}

思路二

上述算法可以优化,求子数组和时不必从头开始,可以直接利用上一次求和的结果,从而可以去掉一层循环.
时间复杂度可以降到O(n^2).
源代码

int MaxSubSum2(const int arr[], int len)
{
    int MaxSum = 0;

    for ( int i=0; i<len; i++){
        int SubSum = 0;
        for ( int j=i; j<len; j++) {
            //caculate the sum of the subsequence with help of the last SubSum.
            SubSum += arr[j];
            if ( SubSum > MaxSum ) {
                MaxSum = SubSum;
            }
        }
    }
    return MaxSum;
}

思路三
采用递归,现将输入数组分解为两个子数组,再递归处理两个子数组,最后将结果合并.即标准的Divide-Conquer-Combine模式.
时间复杂度可以进一步降到O(nlogn)
源代码

int MaxSubSumRec(const int arr[], int left, int right)
{
   //base case.
    if(left == right){
        //TODO:
        return arr[left];
    }
    //divide
    int center = (left+right)/2;
    //conquer
    int MaxLeftSum = MaxSubSumRec(arr, left, center);
    int MaxRightSum = MaxSubSumRec(arr, center+1,  right);
    //combine
    int MaxLeftBorderSum = 0; int LeftBorderSum = 0;
    for(int i=center; i>=left; i--){
        LeftBorderSum += arr[i];
        if(LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    int MaxRightBorderSum = 0; int RightBorderSum = 0;
    for(int i=center+1; i <= right; i++){
        RightBorderSum += arr[i];
        if(RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }
    int max = MaxLeftSum > MaxRightSum?MaxLeftSum:MaxRightSum;
    int LeftRightSum = MaxLeftBorderSum + MaxRightBorderSum;
    max = max>LeftRightSum?max:LeftRightSum;
    return max;
}
int MaxSubSum3(const int arr[], int len)
{
    return MaxSubSumRec(arr, 0, len-1);
}

思路四
输入数组中的若干个负数将数组划分为几个互补重合的子数组,我们只需分别求出这几个子数组的和并比较大小即可.
只需一次循环,时间复杂度为O(n).
源代码

int MaxSubSum4(const int arr[], int len)
{
   int MaxSum =0;
   int SubSum =0;
   for(int i=0; i<len; i++){
       SubSum += arr[i];
       if(SubSum>MaxSum)
           MaxSum = SubSum;
       else if (SubSum < 0 )
           SubSum = 0;
   }
   return MaxSum;
}
Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

 
%d 博主赞过: