剑指offer 连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

模拟退火算法从原理到实战【基础篇】

  模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达...

43660
来自专栏Vamei实验室

纸上谈兵: 数学归纳法, 递归, 栈

数学归纳法 数学归纳法(mathematical induction)是一种数学证明方法,常用于证明命题(命题是对某个现象的描述)在自然数范围内成立。随着现代数...

27060
来自专栏刘望舒

算法(一)时间复杂度

前言 算法很重要,但是一般情况下做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的...

20080
来自专栏琦小虾的Binary

Opencv中数据结构Mat的相关属性

Opencv中数据结构Mat的相关属性 前言: The class Mat represents an n-dimensional dense numeric...

32870
来自专栏专知

【LeetCode 204】关关的刷题日记40 Number of Boomerangs

关关的刷题日记40 – Leetcode 447. Number of Boomerangs 题目 Given n points in the plane th...

36640
来自专栏互联网大杂烩

Python 异常值分析

异常值分析是检验数据是否有录入错误以及含有不合常理的数据。忽视异常值的存在是十分危险的,不加剔除地把异常值包括进数据的计算分析过程中,对结果会产生不良影响;重视...

20420
来自专栏张善友的专栏

EMA算法的C#实现

EMA表示的是指数平滑移动平均,其函数的定义为Y=EMA(X,N) 则Y=[2*X+(N-1)*Y']/(N+1), 其中Y'表示上一周期Y值。 求X的N日指数...

43950
来自专栏逍遥剑客的游戏开发

纹理投影测试

19570
来自专栏肖力涛的专栏

NLP 点滴 :文本相似度 (上)

在自然语言处理过程中,经常会涉及到如何度量两个文本之间的相似性,我们都知道文本是一种高维的语义空间,如何对其进行抽象分解,从而能够站在数学角度去量化其相似性。

2.2K10
来自专栏逍遥剑客的游戏开发

快速LightMap烘焙

11530

扫码关注云+社区

领取腾讯云代金券