最大子陣列
1,暴力法
def getMaxNumList(numlist):
max=0
curtotal=0
startidx = 0
endidx = 0
mylen = len(numlist)
for idx in range(mylen):
curtotal = 0
curtotal += numlist[idx]
for k in range(idx+1,mylen):
curtotal += numlist[k]
if curtotal > max:
max = curtotal
startidx = idx
endidx = k
elif curtotal == max:
print curtotal
print "startidx %s, endidx %s" % (idx,k)
print "startidx %s, endidx %s" % (startidx,endidx)
2, 動態規劃
def MaxSubArray(nums):
n = len(nums)
dp = []
dp.append(nums[0])
mymax = dp[0]
startidx = 0
endidx = 0
for i in range(1, n):
if dp[i-1] + nums[i] <= nums[i] and dp[i-1] + nums[i] > 0:
# print "startidx:%d" % i
startidx = i
dp.append(max(dp[i-1] + nums[i], nums[i]))
if dp[i] > mymax:
# print "endidx:%d" % i
endidx = i
mymax = max(dp[i], mymax)
# print mymax
return mymax, startidx, endidx
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/74629.html
標籤：其他
上一篇：深入理解二叉樹（超詳細）
下一篇：最大子矩陣求解