pat甲级1007 Maximum Subsequence Sum

题意：给你k个数字组成一个串，要求这个串中子串可以得到的最大的值，注意是子串而不是子序列，子序列可以不连在一起，子串必须是连续的一个串。同时还要求最大的子串的开头和结尾（左右值）的值是多少。如果k个数字都是负数，则输出0，和整个串的开头和结尾的值。

分析：动态规划的入门题，可以这样思考，从前往后扫一遍，如果当前的数字+前面的一个子串构成的值>当前数字，那说明你得到前面这个子串肯定是赚的呀，那就收下，连在一起，同时更新一下左右值，左值应该是前面这个子串的左值，右值就是当前数字呗。如果在合并之后得到的值比我们之前得到的最大值大，更新最大值就好了。

 1 #include
 2 #include
 3 #include
 4 using namespace std;
 5 int a[100010];
 6 int dp[100010];
 7 int main()
 8 {
 9     int n;
10     while(cin>>n)
11     {
12         for(int i=0;i)
13         {
14             cin>>a[i];
15             dp[i]=a[i];
16         }
17         int l=a[0],r=a[0],maxx=a[0],al=a[0];
18         for(int i=1;i)
19         {
20             if(dp[i-1]+a[i]>dp[i])
21             {
22                 dp[i]=dp[i-1]+a[i];
23             }
24             else
25             {
26                 l=a[i];
27             }
28             if(dp[i]>maxx)
29             {
30                 maxx=dp[i];
31                 r=a[i];
32                 al=l;
33             }
34         }
35         if(maxx<0)
36         {
37             cout<<"0"<<" "<0]<<" "<1]<<endl;
38             continue;
39         }
40         else
41         {
42             cout<" "<" "<endl;
43         }
44     }
45     return 0;
46 }