最大连续自序列

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<math.h>
 4 #include<string.h>
 5 #include<map>
 6 #include<set>
 7 #include<stdio.h>
 8 #include<stdlib.h>
 9 #define ll long long
10 #define IO ios_base::sync_with_stdio(0);cin.tie(0);
11 using namespace std;
12 int num[10010];
13 int dp[10010];
14 int pos[10010]; //记录起始点
15 int main(){
16     int n;
17     while(cin >> n && n)
18     {
19         memset(num,0,sizeof(num));
20         memset(dp,0,sizeof(dp));
21         memset(pos,0,sizeof(pos));
22         for (int i = 0; i < n; i++)
23         {
24             cin >> num[i];
25         }
26         pos[0] = num[0];
27         int ans = -100;
28         for (int i = 0; i < n; i++)
29         {
30             if (dp[i - 1] + num[i] > num[i])
31             {
32                 pos[i] = pos[i - 1];
33             }
34             else
35             {
36                 pos[i] = num[i];
37             }
38             dp[i] = max(dp[i - 1] + num[i],num[i]);
39             ans = max(ans,dp[i]);
40         }
41         if (ans < 0)
42         {
43             cout << 0 << " " << num[0] << " " << num[n - 1] << endl;
44             continue;
45         }
46         for (int i = 0; i < n; i++)
47         {
48             if (dp[i] == ans)
49             {
50                 cout << dp[i] << " " << pos[i] << " " << num[i] << endl;
51                 break;
52             }
53         }
54 
55     }
56     return 0;
57 }