leetcode--Maximum Subarray

题目链接：https://leetcode.com/problems/maximum-subarray/

算法类型：动态规划

题目分析：最大序列和

代码实现：

 class Solution(object):

     def maxSubArray(self, nums):

         """

         :type nums: List[int]

         :rtype: int

         """

         nums_len = len(nums)

         if nums_len == 1:

             return nums[0]

         mid_len = nums_len / 2

         left_max = self.maxSubArray(nums[ : mid_len])

         right_max = self.maxSubArray(nums[mid_len : ])

         mid_max_1 = nums[mid_len]

         temp = mid_max_1

         for i in range(0, mid_len)[::-1]:

             temp += nums[i]

             mid_max_1 = max(temp, mid_max_1)

         mid_max_2 = nums[mid_len]

         temp = mid_max_2

         for item in nums[ mid_len + 1 : ]:

             temp += item

             mid_max_2 = max(temp, mid_max_2)

         mid_max = mid_max_1 + mid_max_2 - nums[mid_len]

         return max(left_max, right_max, mid_max)

巴特西

leetcode--Maximum Subarray

最新文章

热门文章