如何实现大数据中的最大子序和

如何实现大数据中的最大子序和，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。如输入[-2,1,-3]返回1。

• 第一步，找到中间状态：此处中间状态st[i]表示第i个元素结尾的子数组最大和。

• 第二步，确定状态转移：nums[i]加上一个正数和才会变大，不然还是另起炉灶更有可能得到更大的和。所以当st[i-1]为正数时，st[i]=st[i-1]+nums[i]，否则st[i]=nums[i]。

class Solution:    def maxSubArray(self, nums: List[int]) -> int:        st = nums[0]        for i in range(1,len(nums)):          st.append(max(nums[i],max_list[i-1]+nums[i]))        return max(st)

‍

官方解题视频中给了两个思路，一个是贪心算法：若当前指向元素之前的和小于0，则丢掉当前元素之前的序列；另一个是动态规划：若前一个元素大于0，则将其加到当前元素上。emmm....感觉两种思路很像，不是特别理解本质区别，有兴趣的一起来讨论

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注亿速云行业资讯频道，感谢您对亿速云的支持。