本文讲述了python基础编程100例：第68期-基础数据结构：动态规划 最大子序和！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第68期-基础数据结构：动态规划 最大子序和

1 问题描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

动态规划：

A * "1+1+1+1+1+1+1+1 =？" *

 

A : "上面等式的值是多少"

B : *计算* "8!"

 

A *在上面等式的左边写上 "1+" *

A : "此时等式的值为多少"

B : *quickly* "9!"

A : "你怎么这么快就知道答案了"

A : "只要在8的基础上加1就行了"

A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

由上面的小故事可以知道动态规划算法的核心就是记住已经解决过的子问题的解。

示例 1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2:

输入: nums = [1]

输出: 1

示例 3:

输入: nums = [0,2,3,-3,4,-5,6,-2,8,-4,5,-3,3,3,2,-5,4,-3,3]

输出: 19

示例 4:

输入: nums = [-1]

输出: -1

示例 5:

输入: nums = [-100000]

输出: -100000

初始代码

from typing import List

class Solution:

    def maxSubArray(self, nums: List[int]) -> int:

        #在此之间填写代码

print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

print(Solution().maxSubArray([1]))

print(Solution().maxSubArray([0,2,3,-3,4,-5,6,-2,8,-4,5,-3,3,3,2,-5,4,-3,3]))

print(Solution().maxSubArray([-1]))

print(Solution().maxSubArray([-100000]))

2 解题思路

标签：动态规划

动态规划的是首先对数组进行遍历，当前最大连续子序列和为 a

如果 nums中遍历到的数字与之前的数字之和大于现数字，则直接在nums当前位置修改数值保留并加上当前遍历数字

如果 nums中遍历到的数字与之前的数字之和小于现数字，则nums当前位置数值不变

将列表中最大的数复制给a

3 解题方法

from typing import List

class Solution:

    def maxSubArray(self, nums: List[int]) -> int:

        a,i=nums[0],1

        while i<len(nums):

            nums[i] = max(nums[i - 1] + nums[i], nums[i])

            if nums[i]>a:

                a=nums[i]

            i+=1

        return a

print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

print(Solution().maxSubArray([1]))

print(Solution().maxSubArray([0,2,3,-3,4,-5,6,-2,8,-4,5,-3,3,3,2,-5,4,-3,3]))

print(Solution().maxSubArray([-1]))

print(Solution().maxSubArray([-100000]))

第1-3，12-16行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第4行： 定义变量a和i，分别存放子序列和的最大值以及当前遍历的索引

第5行： 当索引不超过nums的长度时，执行循环

第6行： 给nums列表当前索引位置的元素更换到此索引的最大序列长度

第7行： 判断此序列长度是否大于a

第8行： 若是，则给a赋值最大序列长度

第9行： 每次循环索引加一

第10行： 返回最大序列值

代码运行结果为：

算法讲解

这里用到了基础算法：动态规划，简单讲解下这个算法：

动态规划

动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。

性质

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

3. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

性质

1. 划分：按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的

2. 确定状态和状态变量：将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性

3. 确定决策并写出状态转移方程：状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程

4. 边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。