首页 > 试题广场 >

连续子数组的最大和

[编程题]连续子数组的最大和

热度指数：654809 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

$1 <= n <= 2\times10^5$

$-100 <= a[i] <= 100$

要求:时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$

进阶:时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$

示例1

输入

[1,-2,3,10,-4,7,2,-5]

输出

说明

经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2

输入

[2]

输出

示例3

输入

[-10]

输出

-10

算法知识视频讲解

灰空

用简单的动态规划实现。用f(i)记录以a[i]为结尾的子数组的最大和，如果前面i-1的数组的最大和为负值，则全部抛弃。

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        maxsum = array[0]
        res = maxsum
        for i in range(1,len(array)):
            maxsum = max(maxsum + array[i], array[i])
            res = max(maxsum, res)
        return res

发表于 2019-05-30 09:42:21 回复(0)

更多回答

推荐

信念哥

public class Solution {
     public int FindGreatestSumOfSubArray(int[] array) {
         if (array.length==0 || array==null) {
             return 0;
         }
         int curSum=0;
         int greatestSum=0x80000000;
         for (int i = 0; i < array.length; i++) {
             if (curSum<=0) {
                 curSum=array[i]; //记录当前最大值
             }else {
                 curSum+=array[i]; //当array[i]为正数时，加上之前的最大值并更新最大值。
             }
             if (curSum>greatestSum) {
                 greatestSum=curSum; 
             }
         }
         return greatestSum;
     }
 }

编辑于 2015-07-26 20:51:19 回复(100)

C/C++

kakaan

书本的解法，遍历，遇到负和抛弃之前的结果，重新积累，期间保留最大值

    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty())
            return 0;
        
        int cSum = 0;
        int result = array[0]; // result存储最大和，不能初始为0，存在负数
        for(int i = 0;i<array.size();++i)
        {
            if(cSum < 0) // 当前和<0，抛弃不要
                cSum = array[i];
            else
                cSum += array[i];
            
            if(cSum > result) // 存储最大结果
                result = cSum;
        }
        return result;
    }

发表于 2016-06-27 22:19:53 回复(7)

这人真骚

//直通BAT第二季   左神讲过
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
    if(array.size()<=0)
        return 0;
        int cur,res;
        cur=array[0];       //当前子向量和
        res=cur;            //存储最大的子向量和
        for(int i=1;i<array.size();i++)
            {
            if(cur<0)
                cur=0;
            cur=cur+array[i];
            if(cur>res)
                res=cur;
        }
        return res;
    }
};

发表于 2016-08-20 18:34:04 回复(5)

小新没有蜡笔~

使用动态规划

F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变

F（i）=max（F（i-1）+array[i] ， array[i]）

res：所有子数组的和的最大值

res=max（res，F（i））

如数组[6, -3, -2, 7, -15, 1, 2, 2]

初始状态：

F（0）=6

res=6

i=1：

F（1）=max（F（0）-3，-3）=max（6-3，3）=3

res=max（F（1），res）=max（3，6）=6

i=2：

F（2）=max（F（1）-2，-2）=max（3-2，-2）=1

res=max（F（2），res）=max（1，6）=6

i=3：

F（3）=max（F（2）+7，7）=max（1+7，7）=8

res=max（F（2），res）=max（8，6）=8

i=4：

F（4）=max（F（3）-15，-15）=max（8-15，-15）=-7

res=max（F（4），res）=max（-7，8）=8

以此类推

最终res的值为8

public  int FindGreatestSumOfSubArray(int[] array) {
		int res = array[0];	//记录当前所有子数组的和的最大值
		int max=array[0];	//包含array[i]的连续数组最大值
		for (int i = 1; i < array.length; i++) {
			max=Math.max(max+array[i], array[i]);
			res=Math.max(max, res);
		}
		return res;
}

编辑于 2017-01-23 00:19:54 回复(83)

Python

华科平凡

python solution：


class Solution:
    def FindGreatestSumOfSubArray(self, array):

        if not array:
            return 0

        res,cur=array[0],array[0]
        for i in array[1:]:
            cur+=i
            res=max(res,cur)
            if cur<0:
                cur=0
        return res

发表于 2017-10-19 15:32:35 回复(6)

TX游戏客户端开发内推

/*
C++ 循环 实现
思路：声明一个变量记录遇到的最大的一个值
isInvalidInput用来标记返回0是由于非法输入还是最大和为0
*/
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) 
    {
    	bool isInvalidInput=false;
        if(array.size()==0)
            return 0;
        isInvalidInput=true;
        
        int maxSum=array[0],sum=array[0];
        for(int i=1;i<array.size();i++)
        {
            if(sum>0)
            {
            sum+=array[i];
            if(sum>maxSum)
                maxSum=sum;
            }
            else
            {
                if(array[i]>maxSum)
                    maxSum=array[i];
                sum=array[i];
            }
        }
        return maxSum;
    }
};

发表于 2017-07-25 16:01:17 回复(0)

赵渣渣

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        vector<int> dp(array.size());
        dp[0] = array[0];
        for(int i = 1, size = array.size(); i < size; i++)
        {
            dp[i] = max(array[i], array[i]+dp[i-1]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

发表于 2018-08-07 21:56:59 回复(0)

crazychen

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0) return 0;
        int[] d = new int[array.length];
        d[0] = array[0];
        int max = d[0];
        for(int i=1;i<array.length;i++){
            if(d[i-1]<=0){
                d[i] = array[i];
            }else{
                d[i] = d[i-1]+array[i];
            }
            if(d[i]>max) max = d[i];
        }
        
        return max;
    }
}

发表于 2015-04-12 12:52:08 回复(0)

C++

duerduer冲啊

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

class Solution {
public:
    //相当于array在遍历的过程中充当了存储当前最大数的角色
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size()==1) return array[0];
        int ans = INT_MIN;
        for(int i=1;i<array.size();i++){
            //当前数 和 当前数+前面的累加最大数 求max
            array[i] = max(array[i],array[i]+array[i-1]);
            ans = max(ans,array[i]);
        }
        return ans;
    }
};

发表于 2022-02-01 11:08:25 回复(0)

Java

牛客564955183号

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length;
        int max = 0, i = 0, result = Integer.MIN_VALUE;
        while(i < n) {
            max = max + array[i];
            result = Math.max(result, max);
            if(max < 0) max = 0;
            i++;
        }
        return result;
    }
}

发表于 2021-10-29 17:15:48 回复(0)

C/C++

CCXX201902121547196

class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int sum=0;
int large;//不能初始化，默认比任何数都小
for(int i=0;i<array.size();i++)
{
if (sum<0)
sum=array[i];
else
sum+=array[i]; //如果大于0才相加
if (sum>large)
large=sum;
}
return large;
}

};

出现负数不相加，直接赋值当前值

编辑于 2019-10-03 22:28:16 回复(0)

Java

ReklawPeels

贪心算法
两个序列，A是容忍负数出现的序列，B是不容忍负数出现的序列；
①A每轮选择A和B中值最大的，然后加上当前的数字，无论正负；
②B每轮的选择是，如果B当前数字 >=0 且当前的数字 >0，则自身加上当前数字，否则等于当前数字（这使得B有些名不副实，不过它可以应对全部都是负数的情况）。
③max作为一个统计值，每轮取它自身和A、B3者中最大的一个。

    public int FindGreatestSumOfSubArray(int[] array) {
        int allowNegative = 0, notAllowNegative = 0, max = array[0];
        for (int num : array) {
            int tmp = allowNegative > notAllowNegative ? allowNegative : notAllowNegative;
            allowNegative = tmp + num;
            notAllowNegative = num > 0 && notAllowNegative >= 0 ? notAllowNegative + num : num;
            max = allowNegative > max ? allowNegative : max > notAllowNegative ? max : notAllowNegative;
        }
        return max;
    }

编辑于 2019-05-31 16:23:13 回复(0)

Python

恭喜你又收割一个offer！

把全负的考虑了
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        sumslst = []
        lens = len(array)
        
        if lens < 1:
            return None
        if max(array) < 0:
            return max(array)
        for i in range(lens):
            while lens > 0:
                sums = 0
                for j in range(i, lens):
                    sums += array[j]
                sumslst.append(sums)
                lens -= 1
            lens = len(array)
            
        return max(sumslst)

发表于 2017-07-07 15:58:25 回复(0)

牛客2816108号

《数据结构与算法分析》C语言描述 p21有提到，不过注意：maxSum初始为0是考虑不周全的。

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
    int thisSum,maxSum;
    int size=array.size();
        
        thisSum=0;
        maxSum=array[0];
        
        for(int j=0;j<size;j++){
            thisSum+=array[j];
            if(thisSum>maxSum)
                maxSum=thisSum;
            else if(thisSum<0)
                 thisSum=0;
        }

        return maxSum;
    }
};

发表于 2017-03-03 14:36:15 回复(0)

野魂野胆

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        
        if(array.length==0)return 0;
        
        for(int i = 1 ; i < array.length; i++)
            if(array[i-1]>0) 
                array[i] += array[i-1];
            
        int max = array[0];
        for(int i = 1 ; i < array.length; i++)
            if(array[i] > max)max = array[i];
            
        return max;
        
    }
}

发表于 2016-08-23 17:04:56 回复(3)

VinerL

现在拿n个向量测试，发现结果大多为负，最大的一个是0，Okay，我找到了，然后翻出来一看，这个向量是空的。。。
现在拿n个向量测试，发现n个结果都是0，第一个向量全是0，第二个向量是空的。。。
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size()==0) return 0;
        vector<int> dp(array);
        int re=dp[0];
        for(int i=1;i<array.size();i++){
            if(dp[i-1]>0) dp[i]=dp[i-1]+array[i];
            else dp[i]=array[i];
            if(dp[i]>re) re=dp[i];
        }
        return re;
    }
};

发表于 2016-07-28 15:23:44 回复(0)

林家花美男

看起来我的更好点

class Solution {

public:

int FindGreatestSumOfSubArray(vector<int> array) {

if(array.empty())

return 0;

int max=INT_MIN,i=0,j=array.size(),sum=0;

while(i<j){

sum+=array[i++];

if(sum>max)

max=sum;

if(sum<=0)

sum=0;

}

return max;

}

};

编辑于 2016-06-12 19:20:35 回复(5)

datong

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
    	int len = array.size();
        if(len <= 0) return 0;
        if(len == 1) return array[0];
        vector<int> dp(len,0);
        dp[0] = array[0];
        int m = array[0];
        for(int i = 1; i < len; i ++){
            dp[i] = max(dp[i-1]+array[i],array[i]);
            m = max(dp[i],m);
        }
        return m;
    }
};

简单dp

发表于 2015-09-13 22:29:25 回复(0)

尔玉280615564

public int FindGreatestSumOfSubArray(int[] array) {
		if(array==null||array.length==0)
			return 0;
		int sum=0,maxsum=Integer.MIN_VALUE;
		for (int i = 0; i < array.length; i++) {
			sum+=array[i];
			if(sum>maxsum)maxsum=sum;
			if(sum<0)sum=0;
		}
		return maxsum;
    }

发表于 2015-08-13 11:35:55 回复(1)

牛客000001号

//动态规划 
int FindGreatestSumOfSubArray(vector<int> array) {
		if(array.empty()) return 0;
		int sum = array[0], tempsum = array[0]; //注意初始值 不能设为0 防止只有负数
		for(int i = 1; i < array.size(); i++) //从1开始 因为0的情况在初始化时完成了
		{
			tempsum = (tempsum < 0) ? array[i] : tempsum + array[i];
			sum = (tempsum > sum) ? tempsum : sum;
		}
		return sum;
    }

发表于 2015-07-14 21:47:18 回复(43)

Java

zhaoxfan

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int sum = array[0];
        int former = 0;    //用于记录dp[i-1]的值
        int cur = 0;//用于记录dp[i]的值
        for(int arr : array) {
            cur = arr;
            cur += Math.max(former, 0);
            sum = Math.max(sum, cur);
            former = cur;
        }
        return sum;
    }
}

发表于 2022-08-05 09:20:06 回复(0)

提交观点

问题信息

贪心动态规划

难度：

1685条回答 3063收藏 160909浏览

通过挑战的用户

查看代码

松林子木

2023-03-08 10:26:42
牛客42465...

2023-03-03 20:52:51
Elastic...

2023-02-26 11:32:37
牛客10259...

2023-02-24 16:57:17
牛客94801...

2023-02-18 18:10:42

连续子数组的最大和

输入

输出

说明

输入

输出

输入

输出

python solution：

问题信息

热门推荐

通过挑战的用户

相关试题