/*3.求子数组的最大和（数组）题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n)。例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，因此输出为该子数组的和 18。*/#include <stdio.h>#include <stdlib.h>int Max_Sum(int * a, int len){    int * c = (int *)malloc(sizeof(int) * len); //存包括第i个数字的 a[0]-a[i]的最大子段和    int n = 0; //记录到第几个数字    int maxsum;    c[0] = a[0];    for (n = 1; n < len; n++)    {        c[n] = (c[n - 1] < 0) ? a[n] : c[n - 1] + a[n];    }    maxsum = c[n - 1];    free(c);    int tmpn = len - 1;    while (a[tmpn] < 0)    {        maxsum -= a[tmpn];        tmpn--;    }        return maxsum;}int main(){    int a[8] = {1, -2, 3, 10, -4, 7, 2, -5};    int m = Max_Sum(a, 8);    return 0;}

#define max(a,b) ((a)>(b)?(a):(b))   //定义计算a，b两者中最大值的宏int maxsum(int arr[],int num){    int i;    int maxsofar=0;       //maxsofar记录到目前为止的最大值    int maxendinghere=0;//maxendinghere记录从当前位置开始往前几个连续的数的和的最大值（或0）    for(i=0;i<num;i++)    {        maxendinghere=max(maxendinghere+arr[i],0);        maxsofar=max(maxsofar,maxendinghere);    }    return maxsofar;}