題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1231

題意：

　　給你一個整數序列，求連續子序列元素之和最大，并輸出該序列的首尾元素（若不唯一，輸出首坐標最小的；首坐標相同輸出尾坐標最小的）。

?

題解：

　　O(N)做法。

　　定義sum為當前坐標i之前某一段元素[x,i-1]之和。

　　三種情況：

　　　　（1）sum > 0：說明之前的和對答案有貢獻，更新sum += a[i]，tail = a。

　　　　（2）sum < 0：前面的答案是拖后腿的。。。還不如從a[i]重新開始算,sum = a[i],head = a,tail = a。

　　　　（3）sum = 0：可要可不要。但答案要求首坐標最小，就要了，同sum > 0的情況。

　　如果某次sum > ans，則更新：ans = sum, lef = head, ?rig = tail

?

AC Code:

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #define INF 10000000 5 6 using namespace std; 7 8 int n; 9 int a; 10 int ans; 11 int lef,rig; 12 int start,over; 13 14 int main() 15 { 16 while(cin>>n) 17 { 18 if(n==0) break; 19 int head; 20 int tail=-1; 21 int sum=-INF; 22 ans=-INF; 23 for(int i=0;i<n;i++) 24 { 25 cin>>a; 26 if(i==0) start=a; 27 if(i==n-1) over=a; 28 if(sum>=0) 29 { 30 sum+=a; 31 tail=a; 32 } 33 else 34 { 35 sum=a; 36 head=a; 37 tail=a; 38 } 39 if(sum>ans) 40 { 41 ans=sum; 42 lef=head; 43 rig=tail; 44 } 45 } 46 if(ans>=0) cout<<ans<<" "<<lef<<" "<<rig<<endl; 47 else cout<<"0 "<<start<<" "<<over<<endl; 48 } 49 }

?

?

轉載于:https://www.cnblogs.com/Leohh/p/7376736.html

總結

以上是生活随笔為你收集整理的HDU 1231 最大连续子序列：水dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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