题意：给你k个数字组成一个串，要求这个串中子串可以得到的最大的值，注意是子串而不是子序列，子序列可以不连在一起，子串必须是连续的一个串。同时还要求最大的子串的开头和结尾（左右值）的值是多少。如果k个数字都是负数，则输出0，和整个串的开头和结尾的值。
分析：动态规划的入门题，可以这样思考，从前往后扫一遍，如果当前的数字+前面的一个子串构成的值>当前数字，那说明你得到前面这个子串肯定是赚的呀，那就收下，连在一起，同时更新一下左右值，左值应该是前面这个子串的左值，右值就是当前数字呗。如果在合并之后得到的值比我们之前得到的最大值大，更新最大值就好了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 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<n;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<n;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"<<" "<<a[0]<<" "<<a[n-1]<<endl; 38 continue; 39 } 40 else 41 { 42 cout<<maxx<<" "<<al<<" "<<r<<endl; 43 } 44 } 45 return 0; 46 }
pat甲级1007 Maximum Subsequence Sum
原文：https://www.cnblogs.com/wade1998/p/13449972.html