首页 > 试题广场 > 连续子数组的最大和
[编程题]连续子数组的最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)
推荐
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 回复(78)
使用动态规划
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 回复(61)
动态规划初级题目,做完之后,可以试试最大子矩阵和(https://www.nowcoder.com/questionTerminal/a5a0b05f0505406ca837a3a76a5419b3)
该题目思路:
dp[i]表示以元素array[i]结尾的最大连续子数组和.
以[-2,-3,4,-1,-2,1,5,-3]为例
可以发现,
dp[0] = -2
dp[1] = -3
dp[2] = 4
dp[3] = 3
以此类推,会发现
dp[i] = max{dp[i-1]+array[i],array[i]}.
# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        n = len(array)
        dp = [ i for i in array]
        for i in range(1,n):
            dp[i] = max(dp[i-1]+array[i],array[i])
        
        return max(dp)

发表于 2017-06-18 22:03:25 回复(5)
//动态规划 
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 回复(42)
/*
算法时间复杂度O(n)
用total记录累计值,maxSum记录和最大
基于思想:对于一个数A,若是A的左边累计数非负,那么加上A能使得值不小于A,认为累计值对
          整体和是有贡献的。如果前几项累计值负数,则认为有害于总和,total记录当前值。
此时 若和大于maxSum 则用maxSum记录下来
*/
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0)
            return 0;
        else{
            int total=array[0],maxSum=array[0];
            for(int i=1;i<array.length;i++){
                if(total>=0)
                    total+=array[i];
                else
                    total=array[i];
                if(total>maxSum)
                    maxSum=total;
            }
            return maxSum;
        }
        
    }
}

发表于 2016-05-28 19:02:09 回复(19)
dp入门
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> a) {
    	if(!a.size()) return 0;
        int mx = 0x80000000;
        for(int i = 0, s = 0; i < int(a.size()); ++i){
            s = max(s + a[i], a[i]);
            mx = max(mx, s);
        }
        return mx;
    }
};

发表于 2015-08-23 01:52:49 回复(5)
yzh头像 yzh
让一让   我Python大法来了

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        res =len(array) and max(array)
        temp = 0
        for i in array:
            temp = max(i,temp+i)
            res = max(res,temp)
        return res

发表于 2016-09-01 19:37:24 回复(10)
两种思路:
思路一:基于数组本身特性
# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        if not array:
            return 0
        
        max = array[0]
        sum = array[0]
        
        for num in array[1:]:
            # 当前元素大于连续子数组和加上元素本身并且最大值比元素还小时,
            # 抛弃前面的连续子数组,重新开始计算连续数组和
            if num > (sum + num) and max < num:
                sum = num
                max = num
            # 加上当前元素后,数组和比最大值还大,则连续该元素
            elif sum + num > max:
                max = sum + num
                sum += num
            else:
                sum += num
      	
        return max
            	
思路二:运用动态规划

max[f[i]) 即是最大连续子数组的和
# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        if not array:
            return 0
        
        dp = [array[0]]
        
        i = 1
        for num in array[1:]:
            if dp[i - 1] <= 0:
                dp.append(num)
            else:
                dp.append(dp[i - 1] + num)
            i += 1
        
        return max(dp)
                
            	

编辑于 2016-07-26 16:08:23 回复(3)
书本的解法,遍历,遇到负和抛弃之前的结果,重新积累,期间保留最大值
    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 回复(4)

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)
//直通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)
并不需要DP。
考虑特殊情况,假设最大子数组非负。那么只要扫描一次即可得到答案:
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size() == 0) return 0;
        
    	int max = INT_MIN, sum = 0;
        for(int i=0; i<array.size(); ++i){
            sum += array[i];
            if(sum < 0) sum = 0;
            if(sum > max) max = sum;
        }
        
        return max;
    }
};
现在考虑到最大子数组为负数,最后的结果只可能是最大的那个负数,加上结果为0的特殊情况即可:
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.size() == 0) return 0;
        
    	int max = INT_MIN, sum = 0, min = INT_MIN;
        int flag = 0;
        for(int i=0; i<array.size(); ++i){
            if(array[i] >= 0) flag = 1;
            if(array[i] <= 0 && array[i] > min) min = array[i];
            sum += array[i];
            if(sum < 0) sum = 0;
            if(sum > max) max = sum;
        }
        
        return (flag?max:min);
    }
};

发表于 2015-12-09 21:02:22 回复(5)
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int sum = array[0], maxsum = array[0];
        if(array == null)
            return 0;
        for(int i = 1; i < array.length; i++){
            sum = ( sum < 0 ) ? array[i] : sum + array[i];
            maxsum = ( maxsum < sum ) ? sum : maxsum;
        }
        return maxsum;
    }
}

发表于 2018-08-23 12:02:22 回复(1)
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)
/*
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) {
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)

贪心算法
两个序列,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)
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int max = INT_MIN, sum = 0;
        for(int i = 0; i < array.size(); ++i){
            sum += array[i];         //累加
            if(sum > max) max = sum; //
            if(sum < 0) sum = 0;     //当sum小于0时,就不要在继续往后累加了,因为这样只会越来越小。
        }
        return max;
    }
};

发表于 2017-08-09 14:49:10 回复(1)
把全负的考虑了
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)
《数据结构与算法分析》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)