HDU 1231 最大连续子序列：水dp

题目链接：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:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define INF 10000000

 using namespace std;

 int n;

 int a;

 int ans;

 int lef,rig;

 int start,over;

 int main()

 {

     while(cin>>n)

     {

         if(n==) break;

         int head;

         int tail=-;

         int sum=-INF;

         ans=-INF;

         for(int i=;i<n;i++)

         {

             cin>>a;

             if(i==) start=a;

             if(i==n-) over=a;

             if(sum>=)

             {

                 sum+=a;

                 tail=a;

             }

             else

             {

                 sum=a;

                 head=a;

                 tail=a;

             }

             if(sum>ans)

             {

                 ans=sum;

                 lef=head;

                 rig=tail;

             }

         }

         if(ans>=) cout<<ans<<" "<<lef<<" "<<rig<<endl;

         else cout<<"0 "<<start<<" "<<over<<endl;

     }

 }

巴特西

HDU 1231 最大连续子序列：水dp

最新文章

热门文章