您好,登錄后才能下訂單哦!
題目描述
HZ偶爾會(huì)拿些專業(yè)問題來忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)。今天測(cè)試組開完會(huì)后,他又發(fā)話了:在古老的一維模式識(shí)別中,常常需要計(jì)算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候,問題很好解決。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢?例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開始,到第3個(gè)為止)。給一個(gè)數(shù)組,返回它的最大連續(xù)子序列的和,你會(huì)不會(huì)被他忽悠住?(子向量的長(zhǎng)度至少是1)
# -*- coding: utf-8 -*-
# @Time : 2019-07-09 15:45
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : findGreatestSumofSubArray.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
"""
求連續(xù)子數(shù)組的最大和,其實(shí)就是說從給定數(shù)組中選擇一個(gè)子數(shù)組,使得子數(shù)組的和最大。
解法0:
最樸素的解法,就是遍歷所有可能的子數(shù)組,然后找到和最大的子數(shù)組。共有(1+n)n/2個(gè)子數(shù)組,然后求
和的復(fù)雜度為O(n),也就是這種解法的時(shí)間復(fù)雜度約為O(n^3)
解法1:
維護(hù)兩個(gè)變量,分別記錄當(dāng)前和、最大和,如果當(dāng)前和大于最大和,那么更新最大和。
遍歷整個(gè)數(shù)組,如果加上上一個(gè)元素后當(dāng)前和為負(fù)數(shù),那么當(dāng)前元素不能再與前面元素連起來,
因?yàn)槿魏螖?shù)加負(fù)數(shù)只會(huì)更小。所以當(dāng)前元素需要作為新的子數(shù)組的起點(diǎn),置當(dāng)前和為當(dāng)前元素的值
解法2:
動(dòng)態(tài)規(guī)劃。
dp[i]表示以array中第i個(gè)元素為結(jié)尾的子數(shù)組的最大和
dp[i] = array[i],當(dāng)i=0或dp[i-1]<0
dp[i] = array[i] + dp[i-1],當(dāng)dp[i-1]>=0
"""
def FindGreatestSumOfSubArray1(self, array):
if not array:
raise TypeError("Invalid input")
curSum = 0
greatestSum = -float('inf')
for num in array:
if curSum <= 0:
curSum = num
else:
curSum += num
greatestSum = max(curSum, greatestSum)
return greatestSum
def FindGreatestSumOfSubArray(self, array):
if not array:
raise TypeError("Invalid input")
dp = [array[0]] * len(array)
for i in range(1, len(array)):
if dp[i - 1] < 0:
dp[i] = array[i]
else:
dp[i] = array[i] + dp[i - 1]
return max(dp)
def main():
solution = Solution()
nums = [6, -3, -2, 7, -15, 1, 2, 2]
print(solution.FindGreatestSumOfSubArray(nums))
if __name__ == '__main__':
main()
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。