本文主要是介绍连续子数组的最大和 剑指offer python版,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 题目
- 一、思路
- 二、代码
- 三、总结
题目
题目描述
输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
示例1
输入
[1,-2,3,10,-4,7,2,-5]
返回值
18
说明
输入的数组为{1,-2,3,10,—4,7,2,一5},和最大的子数组为{3,10,一4,7,2},因此输出为该子数组的和 18。
一、思路
【思路】
典型的动态规划。
- 程序运行时,改变数组元素的含义,使得array[n]代表以当前元素为截止点的连续子序列的最大和;
- 如果array[n-1](变化后)>0,array[n](变化后)=array[n](变化前)+array[n-1],因为当前数字加上一个正数一定会变大;
- 如果array[n-1](变化后)<0,array[n](变化后)不变,因为当前数字加上一个负数一定会变小;
- 使用一个变量max记录最大的array值返回即可。
二、代码
# -*- coding:utf-8 -*-
class Solution:def FindGreatestSumOfSubArray(self, array):# write code heremax_val=array[0]for i in range(1,len(array)):array[i]+=max(array[i-1],0)# 使得array[n]代表以当前元素为截止点的连续子序列的最大和;max_val=max(max_val,array[i])# 使用一个变量max记录最大的array值返回return max_val
三、总结
此题可以延伸,记录最佳路径并打印
这篇关于连续子数组的最大和 剑指offer python版的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!