子数组求和最大问题 20131011

问题描述

一个数组中，有整数也有复数，求这个数组的所有子数组中，求和最大的值。

这是一个动态规划问题，乍看上去没有什么简单的方法，把所有的情况列出来就可以了，但是时间复杂度太高了，不是一个很好的算法，必须改变方法。

         我们分解问题，就是b[i] 表示以a[i]结尾的子数组最大的和，那么我们可以动态规划，也可以叫做贪心算法。

         对于b[i] = max( b[i-1] + a[i], a[i]);

         因为对于a[i]结尾的子数组，最大的和有两种情况，一个是他自己，一个是把之前的b[i-1]也加上去。如果b[i-1] > 0 则是选择b[i-1]+a[i] ，反之 选择a[i].

代码：

int getMaxSubArraySum(const int arr[], int &start, int &end , const int length ){

    int b = 0, maxSum = 0;

    int s =0, e= 0;

   

    for( int  i = 0 ; i < length ; ++i){

        if(b > 0 ){

            b += arr[i];

            e = i;

        }else{

            b = arr[i];

            s = i;

            e = i;

        }

 

        if(maxSum < b){

            start = s;

            end = e;

            maxSum = b;

        }

    }

    return maxSum;

}

 

int main()

{

    int a[] = {1,-2,3,10,-4,7,2,-5};

    int start = 0;

    int end = 0;

    cout << "max sum is " << getMaxSubArraySum(a,start,end,sizeof(a)/sizeof(int)) << endl;

    cout << "start:" << start << endl;

    cout << "end  :" << end << endl;

    return 0;

}

 

追梦的飞飞

于广州中山大学 20131011

HomePage: