首页 > 试题广场 >

连续子数组的最大和

[编程题]连续子数组的最大和
  • 热度指数:648747 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,子数组最小长度为1。求所有子数组的和的最大值。
数据范围:



要求:时间复杂度为 ,空间复杂度为
进阶:时间复杂度为 ,空间复杂度为
示例1

输入

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

输出

18

说明

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

输入

[2]

输出

2
示例3

输入

[-10]

输出

-10
推荐
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)
两种思路:
思路一:基于数组本身特性
# -*- 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 回复(4)
书本的解法,遍历,遇到负和抛弃之前的结果,重新积累,期间保留最大值
    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 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)
/*
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)
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)
时间复杂度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)
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)
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:
    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)
现在拿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)
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)
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)
//动态规划 
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)