、
、
，以此类推。我们用
（
，
）表示在第k阶段由初始状态
到下阶段的初始状态
的支路距离。用
（
）表示从第k阶段的
到终点E的最短距离。
和
。若全过程最短路径经过
，则有
（
）= 4 ；若全过程最短路径经过
，则有
（
）= 3 。
点：
，则有
（
，
）+
（
）= 4 + 4 = 8
，则有
（
，
）+
（
）= 6 + 3 = 9
（
）= min（8，9）= 8 ，即由
的最短路径是
，最短距离是8。
点，则有
（
）= min{[
（
，
）+ 
（
）]，[
（
，
）+ 
（
）]}
的最短路径是由
，最短距离是7。
（
）= min ( 6 , 6 ) = 6
的最短路径有两条
和
，其距离都是6。
、
、
如下：
= min( 15 , 14 , 14 ) = 14
= min(11, 12 , 12 ) = 11
= min(14 , 15 , 13 ) = 13
的最短路径有三条
、
、
，最短距离都是14；由
的最短路径是
，距离是11；由
的最短路径有两条：
和
，距离是13。
= min ( 16 , 15 , 16 ) = 15
的全过程最短路径是
，最短距离是15。一个有N个元素的一维数组(a[0], a[1]….a[n-1])，我们定义连续的a[i] ~ a[j]，0<= i, j <=n-1为子数组。
显然这个数组中包含很多子数组，请求最大的子数组之和。
如果不想时间复杂度，用遍历所有可能子数组，然后找出最大值就可以了。
现在如果要求时间复杂度最小，那么肯定是要DP解的。
我们假设定义两个数组：
all[i]：表示从i~n-1，最大的子数组之和。
start[i]：表示包含i，并且从i~n-1，最大子数组之和。
all[i]中max只有三种可能：
(1) a[i]单独就是最大，之后再加一个就会变小。
(2)a[i]+…a[j]最大，即start[i]最大
(3)a[x]+..a[j]最大，即不包含i的后序某一个子数组和最大。
最终，最大的子数组之和是all[0]。根据上述3个可能，很容易写出如下递推式：
start[i] = max (a[i], a[i]+start[i+1])
all[i] = max(start[i], all[i+1])
注意我们把上面max(a, b, c)拆成了两个max(a, b)
由于我们在计算start[i]/all[i]时候需要start[i+?]的值，所以我们从后向前递推dp。
代码如下，时间复杂度O(n)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int
max
(
int
a
,
int
b
)
{
if
(
a
>
b
)
{
return
a
;
}
else
{
return
b
;
}
}
int
max_sum
(
int
*
arr
,
int
n
)
{
// Helper array
int
i
;
int
*
start
=
(
int
*
)
malloc
(
sizeof
(
int
)
*
n
)
;
int
*
all
=
(
int
*
)
malloc
(
sizeof
(
int
)
*
n
)
;
int
final
;
if
(
!
start
||
!
all
)
{
return
-
1
;
}
memset
(
start
,
0
,
sizeof
(
int
)
*
n
)
;
memset
(
all
,
0
,
sizeof
(
int
)
*
n
)
;
// dp
start
[
n
-
1
]
=
arr
[
n
-
1
]
;
all
[
n
-
1
]
=
arr
[
n
-
1
]
;
for
(
i
=
n
-
2
;
i
>=
0
;
i
--
)
{
start
[
i
]
=
max
(
arr
[
i
]
,
arr
[
i
]
+
start
[
i
+
1
]
)
;
all
[
i
]
=
max
(
start
[
i
]
,
all
[
i
+
1
]
)
;
}
final
=
all
[
0
]
;
// Free helper array
free
(
start
)
;
free
(
all
)
;
return
final
;
}
int
main
(
)
{
//int arr[6] = {1, -2, 3, 5, -3, 2}; // 8
int
arr
[
6
]
=
{
0
,
-
2
,
3
,
5
,
-
1
,
2
}
;
// 9
//int arr[5] = {-9, -2, -3, -5, -3}; // -2
printf
(
"max sum of sub_arr: %d \n"
,
max_sum
(
arr
,
sizeof
(
arr
)
/
sizeof
(
int
)
)
)
;
return
0
;
}
|
