/*线性时间算法*/
1 #include<iostream>
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <algorithm>
5 using namespace std;
6 #define NMax 10010
7 int A[NMax];
8
9 int main()
10 {
11 int n = 0;
12 while (scanf("%d", &n), n)
13 {
14 for (int k = 0; k < n; ++k)
15 {
16 scanf("%d", &A[k]);
17 }
18
19 __int64 subSum = 0;
20 __int64 sum = -1;
21 int i = 0;
22 int j = 0; //和不小于0的连续子数组的和的最大下标
23 int nStart = 0;
24 int nEnd = 0; //最大和连续子数组的最大下标
25 for (int k = 0; k < n; ++k)
26 {
27 subSum += A[k];
28 if (subSum < 0)
29 {
30 subSum = 0;
31 i = k + 1;
32 j = k + 1;
33 }
34 else
35 {
36 if (subSum > sum)
37 {
38 sum = subSum;
39 nStart = i;
40 nEnd = k;
41 }
42 }
43 }
44
45 if (sum == -1)
46 {
47 printf("%d %d %d
", 0, A[0], A[n - 1]);
48 }
49 else
50 {
51 printf("%lld %d %d
", sum, A[nStart], A[nEnd]);
52 }
53 }
54 return 0;
55 }
1 /*分治法 子串要么在左边，要么在右边，要么包含中间那个元素*/
2 #include<iostream>
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <algorithm>
6 using namespace std;
7 #define NMax 10010
8 int A[NMax];
9 void AcrossMidMaxSum(int& sum, int left, int mid, int right, int& nStart, int& nEnd)
10 {
11 int leftMaxSum = INT_MIN;
12 int leftSum = 0;
13 for (int i = mid; i >= left; --i)
14 {
15 leftSum += A[i];
16 if (leftSum >= leftMaxSum)
17 {
18 leftMaxSum = leftSum;
19 nStart = i;
20 }
21 }
22
23 int rightMaxSum = INT_MIN;
24 int rightSum = 0;
25 for (int i = mid + 1; i <= right; ++i)
26 {
27 rightSum += A[i];
28 if (rightSum > rightMaxSum)
29 {
30 rightMaxSum = rightSum;
31 nEnd = i;
32 }
33 }
34
35 sum = leftMaxSum + rightMaxSum;
36 }
37
38 void MaxSum(int& sum, int left, int right, int& nStart, int& nEnd)
39 {
40 if (left == right)
41 {
42 sum = A[left];
43 nStart = left;
44 nEnd = right;
45 return;
46 }
47
48 int mid = (left + right) / 2;
49
50 int leftSum = -1, nLeftStart, nLeftEnd;
51 MaxSum(leftSum, left, mid, nLeftStart, nLeftEnd);
52
53 int midSum = -1, nMidStart, nMidEnd;
54 AcrossMidMaxSum(midSum, left, mid, right, nMidStart, nMidEnd);
55
56 int rightSum = -1, nRightStart, nRightEnd;
57 MaxSum(rightSum, mid + 1, right, nRightStart, nRightEnd);
58
59 if (leftSum >= midSum && leftSum >= rightSum)
60 {
61 sum = leftSum;
62 nStart = nLeftStart;
63 nEnd = nLeftEnd;
64 }
65 else if (midSum >= leftSum && midSum >= rightSum)
66 {
67 sum = midSum;
68 nStart = nMidStart;
69 nEnd = nMidEnd;
70 }
71 else
72 {
73 sum = rightSum;
74 nStart = nRightStart;
75 nEnd = nRightEnd;
76 }
77 }
78
79 void Test_1231_1()
80 {
81 int n = 0;
82 while (scanf("%d", &n), n)
83 {
84 for (int k = 0; k < n; ++k)
85 {
86 scanf("%d", &A[k]);
87 }
88 int sum = -1, nStart, nEnd;
89 MaxSum(sum, 0, n-1, nStart, nEnd);
90 if (sum < 0)
91 {
92 printf("%d %d %d
", 0, A[0], A[n - 1]);
93 }
94 else
95 {
96 printf("%d %d %d
", sum, A[nStart], A[nEnd]);
97 }
98 }
99 }
100
101
102 int main()
103 {
104 //Test_1231_0();
105 Test_1231_1();
106 return 0;
107 }