Python最大連續區間和動態規劃
be前言：期末臨近，考Python的同學可以練練
問題描述：給定一段長度為N的整數序列A，請從中選出一段連續的子序列（可以為0）使得這段的總和最大
這裡就不提暴力法瞭，隻能在OJ系統裡得10分（等於沒寫………）下面呈現代碼：
N=int(input().strip()) A=list(map(int,input().strip().split()))#輸入格式 A.insert(0,0)#初始化 N+=1 dp=list(range(N))#dp[i]代表第i個數字結尾的序列最大值 dp[0]=0 if max(A)<=0:#如果全部是負數則不取 輸出0 print(0) else: for i in range(1,N): dp[i]=max(A[i],dp[i-1]+A[i])#下面細說 print(max(dp)) if max(dp)>0 else print(0)#如果最大子序列和小於0 那就幹脆不取 0大於負數 #細說：、 #dp[i]表示第i個數字結尾的子序列最大值 #分析 設第i個數字為a[i] ①dp[i]=a[i]或 (設以a[i]結尾的區間序列和為s1,s2,s3...sn，所以dp[i-1]=max(s1,s2,....sn) dp[i]=max(s1+a[i],s2+a[i]...sn+a[i])=a[i]+max(s1，s2..sn) #即 ②dp[i]=a[i]+dp[i-1] #故第i個數字為結尾的子序列有兩類 所以取較大的值即可
到此這篇關於Python最大連續區間和動態規劃的文章就介紹到這瞭,更多相關Python最大連續區間和動態規劃內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！