描述

給定一個整數數組，找到一個具有最大和的子數組，返回其最大和。

子數組最少包含一個數

您在真實的面試中是否遇到過這個題？
樣例
樣例1:

輸入：[?2,2,?3,4,?1,2,1,?5,3]
輸出：6
解釋：符合要求的子數組為[4,?1,2,1]，其最大和為 6。
樣例2:

輸入：[1,2,3,4]
輸出：10
解釋：符合要求的子數組為[1,2,3,4]，其最大和為 10。

思路 動態規劃

設sum[i]為以第i個元素結尾的最大的連續子數組的和。假設對于元素i，所有以它前面的元素結尾的子數組的長度都已經求得，那么以第i個元素結尾且和最大的連續子數組實際上，要么是以第i-1個元素結尾且和最大的連續子數組加上這個元素，要么是只包含第i個元素，即sum[i]= max(sum[i-1] + a[i], a[i])。可以通過判斷sum[i-1] + a[i]是否大于a[i]來做選擇。因為中間有的sum[i]已經領過加負值變為0啦，后面的sum[i]求和就得根據后面新的數重新計算。 所以最大子序和就是sum[]數組的最大值

代碼1

class Solution:"""@param nums: A list of integers@return: A integer indicate the sum of max subarray"""def maxSubArray(self, nums):# write your code herelength=len(nums) if length==0:return 0for i in range(1,length): #當前值的大小與前面的值之和比較，若當前值更大，則取當前值，舍棄前面的值之和 MaxSum=max(nums[i]+nums[i-1],nums[i]) nums[i]=MaxSum#將當前和最大的賦給nums[i]，新的nums存儲的為和值 return max(nums) nums=[-2,2,-3,4,-1,2,1,-5,3]c=Solution() d=c.maxSubArray(nums) print(d)

結果：6

代碼2：

class Solution:"""@param nums: A list of integers@return: A integer indicate the sum of max subarray"""def maxSubArray(self, nums):# write your code hereif len(nums)==0:return 0presum=maxsum=nums[0]#presum當前和，maxsum最好的和for i in range(1,len(nums)):presum=max(presum+nums[i],nums[i])maxsum=max(maxsum,presum)return maxsumnums=[-2,2,-3,4,-1,2,1,-5,3]c=Solution() d=c.maxSubArray(nums) print(d)

結果：6

代碼3

class Solution:"""@param nums: A list of integers@return: A integer indicate the sum of max subarray"""def maxSubArray(self, nums):# write your code hereif len(nums)==0:return 0presum=[0 for _ in range(len(nums))]presum[0]=nums[0]for i in range(1,len(nums)):presum[i]=max(presum[i-1]+nums[i],nums[i])return max(presum)nums=[-2,2,-3,4,-1,2,1,-5,3]c=Solution() d=c.maxSubArray(nums) print(d)

結果：6

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的LeetCode最大子序和 （动态规划）python的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。