3 微软面试题：求子数组的最大和，并找出此子数组

题目描述：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

下面有个算法时间复杂度为O(n)

#include <iostream>

using namespace std;

int maxArray(int* array, const int&len, int& begin, int& end)//输入数组array和长度，输出最大和数组array（begin,end), 返回值为最大和
{
        int max = array[0];

        int i = 1;
        int b = array[0];
        begin = end = 0;
        int begin1 = -1, end1 = -1;
        while(i < len)
        {
                if(b < 0)
                {
                        b = array[i];
                        begin1 = i;
                        end1 = i;
                }
                else
                {
                        b += array[i];
                                         
                        end1 ++;
                }
                if(max < b)
                {
                        max = b;
                        begin = begin1;
                        end = end1;
                }
                i++;
        }
        return max;
}


int main()
{
        int a[8] = {1,-2,3,10,-4,7,2,-5};
        int cb = 0;
        int ce = 0;
        int len = 8;
        int max = maxArray(a,len,cb,ce);
        cout << "max: " << max << endl;
        cout << "max child array: ";
        for(int i = cb; i <= ce; i++)
        {
                cout << a[i] << ",";
        }
        return 0;
}

输出结果为：

max: 18
max child array: 3,10,-4,7,2

3 微软面试题：求子数组的最大和，并找出此子数组,布布扣,bubuko.com

3 微软面试题：求子数组的最大和，并找出此子数组

原文：http://blog.csdn.net/hhh3h/article/details/20579129