连续子数组的最大和

题目1 连续子数组的最大和

  • 描述: 输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
  • 思路 最大和连续子数组一定有如下几个特点: 1、第一个不为负数 2、如果前面数的累加值加上当前数后的值会比当前数小,说明累计值对整体和是有害的;如果前面数的累加值加上当前数后的值比当前数大或者等于,则说明累计值对整体和是有益的。 步骤: 1、定义两个变量,一个用来存储之前的累加值,一个用来存储当前的最大和。遍历数组中的每个元素,假设遍历到第i个数时: ①如果前面的累加值为负数或者等于0,那对累加值清0重新累加,把当前的第i个数的值赋给累加值。 ②如果前面的累加值为整数,那么继续累加,即之前的累加值加上当前第i个数的值作为新的累加值。 2、判断累加值是否大于最大值:如果大于最大值,则最大和更新;否则,继续保留之前的最大和。 剑指offer之连续子数组的最大和(Python)
  • 实现
def findx(array):
    temp=array[0]
    curSum=0
    for num in array:
        if curSum<=0:
            curSum=num
        else:
            curSum+=num
        if curSum>temp:
            temp=curSum
    return temp

题目1

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端吧啦吧啦

数据结构(二)之算法基础

3827
来自专栏Petrichor的专栏

python: all & any 函数

1022
来自专栏个人随笔

房上的猫:二维数组

二维数组是数组的数组。 二维数组基础   基本的定义方式有两种形式,如:   int [][] i = new int[2][3];(推荐)   int i...

2948
来自专栏前端吧啦吧啦

数据结构(二)之算法基础

1264
来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

4117
来自专栏计算机视觉与深度学习基础

全排列生成算法:next_permutation

概念 全排列的生成算法有很多种,有递归遍例,也有循环移位法等等。C++/STL中定义的next_permutation和prev_permutation函数则...

2126
来自专栏前端儿

三角形面积

输入每行是一组测试数据,有6个整数x1,y1,x2,y2,x3,y3分别表示三个点的横纵坐标。(坐标值都在0到10000之间) 输入0 0 0 0 0 0表示输...

1372
来自专栏数据结构与算法

10:单词排序

10:单词排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入一行单词序列,相邻单词之间由1个或多个空格间隔,请按照...

3707
来自专栏算法channel

Leetcode|Find K Closest Elements

01 — 题目 Given a sorted array, two integers k and x, find the k closest elements ...

3654
来自专栏tkokof 的技术,小趣及杂念

OpenGL ES Shading Language 2.0 参考笔记

声明 struct matStruct { vec4 ambientColor; vec4 diffuseColor; ...

771

扫码关注云+社区