我要招人

去企业版

首页 > 试题广场 >

最大连续数列和

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

热度指数：9023 时间限制：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)

Java

SnailLLL

import java.util.*;

public class MaxSum {
    public int getMaxSum(int[] A, int n) {
        // write code here
        int[] dp=new int[n];
        dp[0]=A[0];
        int max=dp[0];
        for(int i=1;i<n;i++){
            dp[i]=(dp[i-1]>=0)?dp[i-1]+A[i]:A[i];
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}

发表于 2021-10-18 11:40:17 回复(0)

Java

wbsl

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];
        max=max<tem? tem:max;
        if(tem<0)
            tem=0;

        }
        return max;
}
}

发表于 2021-10-10 13:20:01 回复(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)

Java

天山剑客

import java.util.*;

public class MaxSum {
    public int getMaxSum(int[] A, int n) {
        // write code here
    	if (n == 0) {
    		return 0;
    	}
    	
    	int sum = 0;
    	int max_sum = (int) Double.NEGATIVE_INFINITY;
    	for (int i = 0; i < n; i++) {
    		if (sum < 0) {
    			sum = A[i];
    		}else {
    			sum += A[i];
    		}
    		
    		if (sum > max_sum) {
    			max_sum = sum;
    		}
    	}
    	
    	return max_sum;
    }
}

发表于 2019-12-13 19:58:31 回复(0)

Java

我来选个工作

import java.util.*;

public class MaxSum {

public int getMaxSum(int[] A, int n) {

// write code here

int count=0;

int max=A[0];

int flag=A[0];

for(int i=0;i<n;i++){

count+=A[i];

if(count<0) count=0;

if(count>max) max=count;

if(A[i]>flag) flag=A[i];

}

if(flag>0) return max;

else return flag;

}

发表于 2017-06-09 13:45:52 回复(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)