1 題目描述

2 解題思路

2.1 前綴和

建立一個(gè)前綴和數(shù)據(jù)，來記錄 sum(A[0~n])。那么sum(A[i,j])=sum(A[0~j])-sum(A[0~i-1])

class Solution:def maxSubArray(self, nums: List[int]) -> int:tmp=[0]for i in nums:tmp.append(tmp[-1]+i)ma=-1000000l=len(tmp)for i in range(l):for j in range(i+1,l):if(tmp[j]-tmp[i]>ma):ma=tmp[j]-tmp[i]return(ma)

?

這樣是最耗時(shí)的

2.2 動(dòng)態(tài)規(guī)劃

????????我們設(shè)立一個(gè)present_val 表示包括當(dāng)前要遍歷的數(shù)值的情況下，當(dāng)前最大的區(qū)間和

? ? ? ? 其中，present_val滿足：present_val=max(present_val+i,i)

????????present_ret表示目前最大的區(qū)間和，滿足：present_ret=max(present_ret,present_val)

class Solution:def maxSubArray(self, nums: List[int]) -> int:present_val=-100000present_ret=-100000for i in nums:present_val=max(present_val+i,i)present_ret=max(present_ret,present_val)return(present_ret)

?

?2.3 分治

最后一個(gè)做法是leetcode官方給出的一種題解

?

?

import math class Solution:def maxSubArray(self, nums: List[int]) -> int:def get(l,r):if(l==r):#如果只有一個(gè)元素的時(shí)候，回溯return nums[l],nums[l],nums[l],nums[l]else:m=(l+r)//2#尋找中點(diǎn)lSum_l,rSum_l,mSum_l,iSum_l=get(l,m)lSum_r,rSum_r,mSum_r,iSum_r=get(m+1,r)#得到左子區(qū)間和右子區(qū)間的lSum，rSum，mSum和iSumlSum=max(lSum_l,iSum_l+lSum_r)rSum=max(rSum_r,iSum_r+rSum_l)mSum=max(mSum_l,mSum_r,lSum_r+rSum_l)iSum=iSum_r+iSum_lreturn lSum,rSum,mSum,iSumreturn get(0,len(nums)-1)[2]

?

總結(jié)

以上是生活随笔為你收集整理的文巾解题 53. 最大子序和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。