首页 > 试题广场 >

最大连续数列和

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

热度指数：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)

更多回答

小白菜这名字居然有人取了

时间复杂度O(n),空间复杂度O(1)，动态规划
class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        // write code here
    	int dp0 = A[0], max = A[0];
        for(int i = 1; i < n; i++)
        {
        	if(dp0 + A[i] > A[i])
        		dp0 = dp0 + A[i];
        	else
        		dp0 = A[i];
        	if(dp0 > max)
        		max = dp0;
        }
        return max;
    }
};

发表于 2016-05-16 22:33:55 回复(0)

919323

class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        // write code here
        int sum = 0;
        int max = 0;
        for(int i = 0; i < n; ++i){
            sum += A[i];
            if(sum > 0)
                max = max < sum ? sum : max;
            else
                sum = 0;
        }
        return max;
    }
};

发表于 2015-10-02 13:35:04 回复(2)

Ansel

class MaxSum {

public:

int getMaxSum(vector<int> A, int n) {

// write code here

//编程珠玑第八章扫描算法，时间复杂度O(n)

int MaxSum=0,sum=0;

for (int i=0;i<A.size();i++)

{

sum+=A[i];

if (sum>0)

{

if (MaxSum<sum)

MaxSum=sum;

}

else

sum=0;

}

return MaxSum;

}

};

发表于 2015-11-24 09:36:29 回复(1)

xuangev5

//简单动态规划
class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        // write code here
        int curSum = A[0];
        int res = A[0];
        for(int i =1; i<n; i++){
            curSum = max(A[i],curSum + A[i]);
            res = max(res,curSum);
        }
        return res;
    }
};

发表于 2015-08-17 21:37:41 回复(0)

Java

Simms

    public int getMaxSum(int[] A, int n) {
        // write code here
        int res = A[0];
        for(int i = 1; i< A.length; i++){
            A[i] += Math.max(A[i-1], 0);
            res = Math.max(res, A[i]);
        }
        return res;
    }

发表于 2020-07-12 15:48:01 回复(0)

ID84848484

import java.util.*;

public class MaxSum {
    public int getMaxSum(int[] A, int n) {
        // write code here
        int ret=Integer.MIN_VALUE;
        int sum=0;
        for(int i=0;i<n;i++){
            if(A[i]+sum>=A[i]){
                sum+=A[i];
            }
            else
            {
                sum=A[i];
            }
            ret=Math.max(ret,sum);
        }
        return ret;
    }
}

发表于 2019-05-27 14:54:18 回复(0)

木然猫猫

时间复杂度：O(n) 空间复杂度：O(1)

class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        int res = INT_MIN;
        int pre = 0;
        for (int i : A) {
            pre = max(pre + i, i);
            res = max(res, pre);
        }
        return res;
    }
};

发表于 2018-12-29 11:05:18 回复(0)

小学作业多

第一种：暴力求解，时间复杂度O(n^2)

int getMaxSum(vector<int> A, int n) {
	// write code here
	int cur_sum, max_sum = INT_MIN;
	for (int i = 0; i < n; i++)		// i是子列左端位置
	{
		cur_sum = 0;    // this_sum是子列A[i]...A[j]的和 
		for (int j = i; j < n; j++)	// j是子列右端位置
		{
			cur_sum += A[j];
			if (cur_sum > max_sum)
				max_sum = cur_sum;
		}
	}
	return max_sum;
}

第二种：分而治之，时间复杂度O(nlogn)

int getMaxSum(vector<int> A, int n) {
	// write code here
	return maxSumRec(A, 0, n - 1);
}

int maxSumRec(vector<int> A, int left, int right)	// 递归求解，复杂度O(nlogn) 
{
	if (left == right)    // 递归终止条件，子列只有1个数字
		return A[left];
	/*  下面是"分"的过程  */
	int mid = (left + right) / 2;
	int maxLeftSum = maxSumRec(A, left, mid);		// 递归求解左半部分
	int maxRightSum = maxSumRec(A, mid + 1, right); // 递归求解右半部分

	/*  下面求跨分界线的最大子列和  */
	// 求出左半部分包含最后一个元素的最大子序列和 
	int leftBorderSum = 0, maxLeftBorderSum = INT_MIN;
	for (int i = mid; i >= left; i--)        // 从中线向左扫描
	{
		leftBorderSum += A[i];
		if (leftBorderSum > maxLeftBorderSum)
			maxLeftBorderSum = leftBorderSum;
	}
	// 求出右半部分包含第一个元素的最大子序列和 
	int rightBorderSum = 0, maxRightBorderSum = INT_MIN;
	for (int j = mid + 1; j <= right; j++)    // 从中线向右扫描
	{
		rightBorderSum += A[j];
		if (rightBorderSum > maxRightBorderSum)
			maxRightBorderSum = rightBorderSum;
	}

	return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

int max3(int a, int b, int c)	// 求出三者中的最大值 
{
	int max = a;
	if (max < b) max = b;
	if (max < c) max = c;
	return max;
}

第三种：动态规划，时间复杂度O(n)

int getMaxSum(vector<int> A, int n) {
	// write code here
	int cur_sum = 0, max_sum = INT_MIN;
	for (int i = 0; i < n; i++)
	{
		cur_sum += A[i];		// 向右累加
		if (cur_sum > max_sum)
			max_sum = cur_sum;	// 发现更大和则更新当前结果
		if (cur_sum < 0)		// 如果当前子列和为负
			cur_sum = 0;		// 则不可能作为最大子列的前缀，扔掉
	}
	return max_sum;
}

编辑于 2017-07-28 17:46:18 回复(0)

蓝魔4

class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        vector<int> B(n);
        B[0]=A[0];
        int max=B[0];
        for(int i=1;i<n;i++)
        {
            int tmp=B[i-1]+A[i];
            if(tmp>A[i])
                B[i]=tmp;
            else
                B[i]=A[i];
            if(B[i]>max)
                max=B[i];
        }
        return max;
    }
};

发表于 2017-07-27 12:23:08 回复(0)

阿狸不是猫

import java.util.*;
/*
思路：从第一个数开始加，如果加上这个数的和小于0，那就从下一个数重新开始加，记录过程中出现的最大值即可
我觉得这道题目是可以推广到计算最大值对应的连续数列区间，计算区间就需要保存每次max值变更的时候的start
和end位置
*/
public class MaxSum {
    public int getMaxSum(int[] A, int n) {
        int max=A[0];
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=A[i];
            max=Math.max(sum,max);
            if(sum<0) sum=0;
        }
        return max;
    }
}
运行时间：92ms
占用内存：11460k

发表于 2017-07-06 11:11:37 回复(0)

Cavs

class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) 
    {
        int res = INT_MIN;
        int curSum = 0;
        for(auto& i:A)
        {
            curSum += i;
            res = max({res,curSum,i});
            if(curSum < 0) curSum = 0;
        }
        
        return res;
    }
};

发表于 2017-06-29 22:35:21 回复(0)

C/C++

牛客9863708号

class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        
        if(n<=0){
            return 0;
        }
        
        int temp = A[0];
        int max = A[0];
         
        for(int i=1; i<n; i++){
            if(temp>=0){
                temp += A[i];
                if(temp>0){
                    if(temp>max){
                        max = temp;
                    }
                }else{
                    temp = 0;
                }
            }else{
                if(A[i]>0){
                    temp = A[i];
                    max = temp;
                }else{
                    if(temp < A[i]){
                        temp = A[i];
                        max = temp;
                    }
                }
            }
        }
        return max;
    }
};

发表于 2017-05-27 15:34:41 回复(0)

=..=

class MaxSum {
public:
int getMaxSum(vector<int> A, int n) {
// write code here
int len=A.size();
if(len<=0)return 0;
if(len==1)return A[0];
int sum=0;int max=A[0];
for(int i=0;i<len;i++){
sum+=A[i];
if(sum<0){
sum=0;
}
max=max<sum?sum:max;
}
return max;
}
};

发表于 2017-03-16 10:21:00 回复(0)

Aurora1

class MaxSum:
    def getMaxSum(self, A, n):
        s, m = 0, A[0]
        for i in xrange(n):
            s += A[i]
            if s > m:
                m = s
            elif s < 0:
                s = 0
        return m

发表于 2017-03-11 20:34:30 回复(0)

Java

蓝胖子SHD

import java.util.*;

public class MaxSum {
    public int getMaxSum(int[] A, int n) {
        // write code here
        int max=Integer.MIN_VALUE;
		int tem=0;
		for (int i = 0; i < A.length; i++) {
			tem+=A[i];
			if(tem<0){
				tem=0;
			}else{
				max=max<tem?tem:max;
			}
		}
		return max;
    }
}

发表于 2016-08-15 23:23:13 回复(3)

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)

已注销

class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        // write code here
        if(n<=0) return 0;
        if(n==1) return A[0];
        int sum=A[0];
        int curmax=A[0];
        int i;
        for(i=1;i<A.size();i++)
        {
            curmax=(curmax<0)?A[i]:curmax+A[i];
            sum=(curmax>sum)?curmax:sum;
        }
        return sum;
    }
};

发表于 2016-07-22 14:31:13 回复(0)

牛客728491号

int getMaxSum(vector<int> A, int n) {
    int max = 0, sum = 0;
    for(int i = 0; i < n; i++) {
        sum += A[i];
       max = sum > max ? sum : max;
        sum = sum < 0 ? 0 : sum;  
    }
    return max;
}

题目中说数组数字有正有负，所以不用考虑没有正数的情况。

发表于 2016-05-03 11:13:27 回复(0)

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)

C++

好菜啊我

/*
思路1：动态规划

状态定义：
F[i]：以i下标为结尾的子序列的最大和

在子序列的求和过程中，遵循的原则是，如果加上某个数对最大和有利那么就加上，如果不利就不加。
因此以i下标为结尾的子序列的最大和 = max（以i-1为下标的子序列的和+A[i]，A[i]）
也就是说，如果A[i]加上前一个子序列，所得值反而小于A[i]本身，那么干脆就让A[i]自身作为一个新的最大子序列。

状态转移方程：
F[i] = max(F[i-1]+A[i],A[i]);

状态初始化：
F[0] = A[0]

*/
/*
class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        //校验数据合法性
        if(A.size()==0 || n<=0){
            return 0;
        }

        vector<int> F(n);
        F[0] = A[0];

        //状态转移方程
        for(int i=1;i<n;i++){
            F[i] = max(F[i-1]+A[i],A[i]);
        }
        //排升序，便于获取最大和
        sort(F.begin(),F.end());

        return F[n-1];
    }
};
*/

/*
思路2：贪心

其实和动态规划类似：有利于我的我就要，不利于我的我不要

*/

class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        //校验数据合法性
        if(A.size()==0 || n<=0){
            return 0;
        }

        //防止数组全是负数
        int sum = A[0];
        int totalSum = A[0];

        //从第二个元素开始
        for(int i=1;i<n;i++){
            if((sum+A[i]) >= A[i]){
                //当前数加上前一个数组的最大和有利于当前数，因此加上
                sum += A[i];
            }else{
                //当前数加上前一个数组的最大和不利于当前数，因此当前数重新作为一个数组的开头开始找
                sum = A[i];
            }
            //每找完一个树，都要判断最大值
            totalSum = max(totalSum,sum);
        }

        return totalSum;
    }
};

发表于 2023-04-11 17:22:08 回复(0)