计算最大的连续K的整数的和

题目如下：

3.求子数组的最大和

题目：

输入一个整形数组，数组里有正数也有负数。

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

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

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，

因此输出为该子数组的和18。

解题方法为mark allen weiss的数据结构与问题求解的内容。即线性扫描。如果当前sum值是正数则继续扫描。每次扫描的时候比较是否是最大值。如果当前sum值为0或者负数则从下一个数开始扫描。

这个是代码。

活动地址

/*
 * maxN.c
 *
 *  Created on: 2011-10-26
 *      Author: blacksapper
 */
#include <stdio.h>
#include <stdlib.h>
typedef struct maxN{
    int startnum;
    int endnum;
    int sum;
}maxN,*maxList;

maxList max;
maxList temp;
int test[8]={1, -2, 3, 10, -4, 7, 2, -5};
int Next(int *a,int len){
    /**
     * 初始化*/
    int i=0;
    //int sum=0;
    if(!max)
        return -1;
    if(!temp)
        return -1;
    max->endnum=-1;
    max->startnum=-1;
    max->sum=-2147483647;
    temp->endnum=1;
    temp->startnum=1;
    temp->sum=0;
    //sum=a[0];
    /*运算模块*/
    for(;i<len;i  ){
        temp->sum =a[i];
        if(temp->sum<=0){/*如果sum小于0则放弃当前过程走下一个过程*/
            temp->startnum=i 1;
            temp->endnum=i 1;
            temp->sum=0;
            continue;
        }else{
            if(temp->sum<max->sum)
                continue;
            else