子数组最大和

昨天笔试看到一个求子数组最大和,参考这里,http://blog.csdn.net/v_JULY_v/…,写了一下,复杂度 O(n)

#include <stdio.h>

int max_sum(int *a, int n)
{
	int max = a[0];
	int sum = 0;
	for (int i=0; i<n; i++)
	{
		if (sum < 0)
		{
			sum = a[i];
		}
		else
		{
			sum += a[i];
		}
		if (sum > max)
		{
			max = sum;
		}
	}
	return max;
}

int main()
{
	int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
	printf("%dn", max_sum(a, sizeof(a)/sizeof(int)));
}

Leave a Reply

Your email address will not be published. Required fields are marked *