H面试（23）：求子数组最大和

题目描述：
输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

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

#include<stdio.h>

#include<malloc.h>

#include<assert.h>

int max_subarray_sum(int * a, int num)

{   

	assert(a);

	int sum = 0;   //遍历数组值，存放和值

	int max =a[0];    //存放当前的子数组的最大值

    int j = 0;     //记录当前i的位置

	int i;         //遍历数组的计数器

	for(i = 0; i < num;  )  //循环遍历数组

	{

		sum = sum + a[i]; 

        if(sum > max)    //如果相加的结果大于max，就更新max，记录下当前i的位置

		{

			max = sum;

			i++;

		    j=i;

		}

		else if( sum < 0) //如果sum的值小于0，就代表之前的子数组相加结果不理想，sum归零，从下一个i开始重新算

		{

			sum = 0;

			i = j;

			i++;

		}

		else  //此处代表这，sum的值没有打过max，但sum的值也没有小于零：遇到了一个非正数，可能下个数就是更大的整数，所以继续循序

			i++;

		    j=i;

	}

	if(i = num-1 && max < 0)  //这个可以避免全部是负数的情况

	{

		for(i = 1; i < num; i++)

		{

			if(a[i] >max)

		     max = a[i];

		}

	}

	return max;

}

int main( )

{

	int a[] = {-3,-2,0};

	int num = sizeof(a)/sizeof(int);

	int max_subarray_sum = max_subarray_sum( a, num);

	printf("%d\n",max_subarrya_sum);

	return 0;

}

//copyright@ July

//July、updated，2011.05.25。

#include <iostream.h>

#define n 4           //多定义了一个变量   

int maxsum(int a[n])

//于此处，你能看到上述思路2代码（指针）的优势

{

    int max=a[0];       //全负情况，返回最大数

    int sum=0;

    for(int j=0;j<n;j++)

    {

        if(sum>=0)     //如果加上某个元素，sum>=0的话，就加

            sum+=a[j];

        else

            sum=a[j];  //如果加上某个元素，sum<0了，就不加

        if(sum>max)

            max=sum;

    }

    return max;

}  

int main()

{

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

    cout<<maxsum(a)<<endl;

    return 0;

}  

H面试（23）：求子数组最大和的相关教程结束。