#include
<
iostream
>
#include
<
stdio.h
>
const
int
MIN
=
-
999999999
;
//
定义MIN为只读变量 为一个非常小的值
int
a[
100001
];
int
ans[
100001
];
using
namespace
std;
int
main(){
int
n;
int
an;
while
(scanf(
"
%d
"
,
&
n)
!=
EOF) {
if
(n
==
0
)
break
;
int
sum
=
0
;
int
k
=
MIN;
for
(
int
i
=
1
;i
<=
n;i
++
) { scanf(
"
%d
"
,
&
a[i]); sum
+=
a[i];
if
(sum
>
k) k
=
sum; ans[i]
=
k;
//
第i个数前的最大连续和为ans[i]
if
(sum
<
0
)
//
如果sum<0 则舍弃前面的数 sum从下一个数开始加
sum
=
0
; } sum
=
0
; k
=
an
=
MIN;
for
(
int
j
=
n;j
>
1
;j
--
)
//
反方向查找
{ sum
+=
a[j];
if
(sum
>
k) k
=
sum;
if
(an
<
(ans[j
-
1
]
+
k))
//
从后数前n-j+1个数的最大连续和k 加上 正数第j-1个数的最大连续和
an
=
ans[j
-
1
]
+
k;
//
用an
if
(sum
<
0
)
//
如果sum<0 则舍弃前面的数 sum从下一个数开始加
sum
=
0
; } printf(
"
%d\n
"
,an); }
return
0
;}
转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048224.html
