首页 > 代码库 > 剑指Offer:连续子数组的最大和

剑指Offer:连续子数组的最大和

题目: 输入一个整型数组, 数组里有正数也有负数. 数组中的一个或连续的多个整数组成一个子数组. 求所有子数组的和的最大值. 要求时间复杂度为O(n)

#include <stdio.h>int maxsum_subarray(int a[], int n){    if( a==NULL || n<=0 )    {        printf("Error.\n");        return 0x80000000;    }    int i;    int curmax = 0x80000000;    int cursum = 0;    for( i=0; i<n; i++ )    {        if( cursum <= 0 ) // 当前元素之前的若干个元素之和已经<=0; 以当前元素为起点, 继续往后求子数组的和            cursum = a[i];        else            cursum += a[i];        if( cursum > curmax ) // 更新新的最大值            curmax = cursum;    }    return curmax;}int main(void){    int a[] = {19,-20,3,10,-4,7,2,-5};    int result = maxsum_subarray(a,8);    printf("%d\n", result);    return 0;}