最大连续数列和

[编程题]最大连续数列和

热度指数：9013 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个有正有负的整数数组A及其大小n，返回从前往后相加最大的连续数列的和。保证n的大小小于等于3000。

测试样例：

[1,2,3,-6,1]

返回：6

算法知识视频讲解

查看答案及解析

推荐

思路：时间复杂度O(n),空间复杂度O(1)
1.首先定义一个和的最小值
2.遍历开始累加 一开始是最小值 ，所以 sum += A[0];sum > max; max 就为A[0]; 判断如果sum 是小于0，重置sum = 0， （累加的初始值还应从0 开始），因为我们把值存在了max中，所以sum 重置为0 不影响max的变化，所以每次比较 sum 和 max 就好
3.这种解法 还有利于求解 产生最大值的区间位置
4.区间位置：就是最后一次更新 sum = 0时，和最后一次max 更新时的位置 即可

int getMaxSum(vector<int> A, int n) {
        // write code here
        int sum = 0;
        int max = -(1 << 30);
        for(int i=0;i<n;i++)
            {
            sum += A[i];
            if(sum > max)
            {
                max = sum;
            }
            if(sum < 0)
                {
                sum = 0;
            }
        }
        return max;
    }

编辑于 2015-08-18 18:40:59 回复(2)

Python

华科平凡

python solution

# -*- coding:utf-8 -*-

class MaxSum:
    def getMaxSum(self, A, n):
        res=A[0]
        tmp=0
        for i in A:
            tmp+=i
            res=max(res,tmp)

            if tmp<0:
                tmp=0

        return res

发表于 2017-10-31 17:21:22 回复(0)

Python

Yannyezixin

不同于面试金典里思路,这是剑指offer里的思路：

同样维持一个最大值，唯一不同的是sum的值

当sum < 0时， sum 赋值为A[i],否则加上A[i]

# -*- coding:utf-8 -*-

class MaxSum:
    def getMaxSum(self, A, n):
        if n < 1:
            return 0
        
        sum = A[0]
        max = A[0]
        for i in range(1, n):
            if sum < 0:
                sum = A[i]
            else:
                sum += A[i]
            if max < sum:
                max = sum
        return max

发表于 2016-08-10 10:12:26 回复(0)