求解該問(wèn)題的四種算法：
時(shí)間O(N3)，算法一
int
?MaxSubsequenceSum(
const
?
int
?A[],
int
?N)
{
????
int
?ThisSum,MaxSum,i,j,k;
????
????MaxSum?
=
?
0
;
????
for
(i?
=
?
0
;i?
<
?N;i
++
)
????????
for
(j?
=
?i;j?
<
?N;j
++
)
????????
{
????????????ThisSum?
=
?
0
;
????????????
for
(k?
=
?i;k?
<=
?j;k
++
)????ThisSum?
+=
?A[k];????????????????
????????????
if
(ThisSum?
>
?MaxSum)????MaxSum?
=
?ThisSum;
????????}
????????
????
return
?MaxSum;
}
時(shí)間O(N2)，算法二
int
?MaxSubsequenceSum(
const
?
int
?A[],
int
?N)
{
????
int
?ThisSum,MaxSum,i,j;
????
????MaxSum?
=
?
0
;
????
for
(i?
=
?
0
;i?
<
?N;i
++
)
????
{
????????ThisSum?
=
?
0
;
????????
for
(j?
=
?i;j?
<
?N;j
++
)
????????
{
????????????ThisSum?
+=
?A[k];????????????????
????????????
if
(ThisSum?
>
?MaxSum)????MaxSum?
=
?ThisSum;
????????}
????}
????????
????
return
?MaxSum;
}
時(shí)間O(NlogN)，算法三
static
?
int
?MaxSubSum(
const
?
int
?A[],
int
?Left,
int
?Right)
{
????
int
?MaxLeftSum,MaxRightSum;
????
int
?MaxLeftBorderSum,MaxRightBorderSum;
????
int
?LeftBorderSum,RightBorderSum;
????
int
?Center,i;
????
????
if
(Left?
==
?Right)
????????
if
(A[left]?
>
?
0
)????
return
?A[left];
????????
else
????
return
?
0
;
????????????
????Center?
=
?(Left?
+
?Right)?
/
?
2
;
????MaxLeftSum?
=
?MaxSubSum(A,Left,Center);
????MaxRightSum?
=
?MaxSubSum(A,Center?
+
?
1
,Right);
????
????MaxLeftBorderSum?
=
?
0
;
????LeftBorderSum?
=
?
0
;
????
for
(i?
=
?Center;i?
>=
?Left;i
--
)
????
{
????????LeftBorderSum?
+=
?A[i];
????????
if
(LeftBorderSum?
>
?MaxLeftBorderSum)????MaxLeftBorderSum?
=
?LeftBorderSum;
????}
????
????MaxRightBorderSum?
=
?
0
;
????RightBorderSum?
=
?
0
;
????
for
(i?
=
?Center?
+
?
1
;i?
<=
?Right;i
++
)
????
{
????????RightBorderSum?
+=
?A[i];
????????
if
(RightBorderSum?
>
?MaxRightBorderSum)????MaxRightBorderSum?
=
?RightBorderSum;
????}
????
????
return
?Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum?
+
?MaxRightBorderSum);
}
int
?MaxSubsequenceSum(
const int??A[],int
?N)
{
????
return
?MaxSubSum(A,
0
,N?
-
?
1
);????
}
時(shí)間O(N)，算法四
intMaxSubsequenceSum(
const int
?A[],
int
?N)
{
????
int
?ThisSum,MaxSum,i;
????
????ThisSum?
=
?MaxSum?
=
?
0
;
????
for
(i?
=
?
0
;i?
<
?N;i
++
)
????
{
????????ThisSum?
+=
?A[i];
????????
if
(ThisSum?
>
?MaxSum)
????????????MaxSum?
=
?ThisSum;
????????
else
????????????ThisSum?
=
?
0
;
????}
????
????
return
?MaxSum;
}
參考《數(shù)據(jù)結(jié)構(gòu)與算法分析》