最大连续子序列和

题目描述

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解答

思路

个人认为 该题还是很值得研究的
解答思路，这位大佬说的很好解题思路

python3 代码实现

该代码是根据这大佬的思路实现的

class Solution:
    @staticmethod
    def maxSubArray_brudeforce(nums):
        \'\'\'
        该算法的时间复杂度是 0(n^2)
        :param nums:
        :return:
        \'\'\'
        max_sum = nums[0]
        nums_len = len(nums)
        for i in range(nums_len):
            this_sum = 0
            for j in range(i,nums_len):
                this_sum += nums[j]
                if this_sum>max_sum:
                    max_sum=this_sum
        return max_sum

    @staticmethod
    def maxSubArray_Divide(nums):
        \'\'\'
        概算法的时间复杂度是O(NlogN)
        这里有一个数据操作技巧：（l+r）//2
        :param nums:
        :return:
        \'\'\'

        def solution(l,r):
            if l>=r:
                return nums[l]
            m = (l+r)//2
            #考虑特殊的一种情况 横跨左右两个
            #左面
            lmax = nums[m]
            lsum = 0
            for i in range(m,l-1,-1):
                lsum += nums[i]
                if lsum > lmax:
                    lmax = lsum

            rmax = nums[m+1]
            rsum = 0
            for i in range(m+1,r+1):
                rsum += nums[i]
                if rsum > rmax:
                    rmax = rsum
            return max(lmax+rmax,solution(l,m),solution(m+1,r))


        return solution(0,len(nums)-1)





    @staticmethod
    def maxSubArray_most(nums):
        \'\'\'
        这个算法的时间复杂度为O(n)
        :param nums:
        :return:
        \'\'\'

        max_sum = nums[0]
        sum=0
        for num in nums:
            if sum>0:
                sum+=num
            else:
                sum=num

            max_sum=max(max_sum,sum)
        return max_sum









if __name__==\"__main__\":
    nums=[-84,-87,-78,-16,-94,-36,-87,-93,-50,-22,-63,-28,-91,-60,-64,-27,-41,-27,-73,-37,-12,-69,-68,-30,-83,-31,-63,-24,-68,-36,-30,-3,-23,-59,-70,-68,-94,-57,-12,-43,-30,-74,-22,-20,-85,-38,-99,-25,-16,-71,-14,-27,-92,-81,-57,-74,-63,-71,-97,-82,-6,-26,-85,-28,-37,-6,-47,-30,-14,-58,-25,-96,-83,-46,-15,-68,-35,-65,-44,-51,-88,-9,-77,-79,-89,-85,-4,-52,-55,-100,-33,-61,-77,-69,-40,-13,-27,-87,-95,-40]
    print(Solution.maxSubArray_most(nums))