题目：输入一个整型数组,数组里有整数也有负数。
数组中一二或连续的多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)
思路：动态规划，分别计算第i时刻（0<=i<=n）之前子数组的最大和，如果第i-1时刻的值为负值，则将其丢弃，则当前最大和为当前数组位置的值，若不为负数，则将其加上当前位置的值。
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
alist = [0]*len(array)
for i in range(len(array)):
if i==0 or alist[i-1]<0:
alist[i] = array[i]
else:
alist[i] = alist[i-1] + array[i]
return max(alist)
剑指Offer 42：连续子数组最大和 Leetcode 53. Maximum Subarray 思路比较简单：...
剑指 Offer 42. 连续子数组的最大和[https://leetcode-cn.com/problems/l...
面试 20：计算连续子数组的最大和（剑指 Offer 31 题） 我们上一次推文留下的题目来源于《剑指 Offer...
title: 每日一练（22）：连续子数组的最大和 categories:[剑指offer] tags:[每日一练...
本文首发于我的个人博客：尾尾部落 题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后...
题目 输入一个整型数组，数组里有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要...
1. 题目 2. 解答 初始化 sum=0，然后遍历数组进行累加。如果 sum 变为负数，也就说再继续累加的话贡献...
1、题目描述 输入一个 非空 整型数组，数组里的数可能为正，也可能为负。 数组中一个或连续的多个整数组成一个子数组...
前言 本文是《剑指Offer》系列（JavaScript版）的第一篇，题目是“连续子数组的最大和或最小和”。 话不...
题目：输入一个整型数组,数组里有整数也有负数。数组中一二或连续的多个整数组成一个子数组。求所有子数组的和的最大值。...
本文标题：剑指offer面试题----连续子数组的最大和
本文链接：https://www.haomeiwen.com/subject/usvrdxtx.html
网友评论