基本题二：最大字段和问题
一、实验目的与要求
1、熟悉最长最大字段和问题的算法；
2、进一步掌握动态规划算法；
二、实验题
若给定n个整数组成的序列a1，a2，a3，...，an，求该序列形如ai＋ai＋1＋...＋an的最大值。
三、实验提示
|
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
|
int
MaxSum(
int
n,
int
*a,
int
&besti,
int
&bestj)
{
int
sum=0;
for
(
int
i=1;i<=n;i++)
for
(
int
j=i;j<=n;j++)
{
int
thissum=0;
for
(
int
K=i;k<=j;k++)thissum+=a[k];
if
(thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
return
sum;
}
intMaxSum(
int
n,
int
*a,
int
&besti,
int
&bestj)
{
int
sum=0;
for
(inti=1;i<=n;i++)
{
int
thissum=0;
for
(intj=i;j<=n;j++)
{
thissum+=a[j];
if
(thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
}
return
sum;
}
|
四、源代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public
static
void
main(String[] args) {
int
[] a = {
12
,
8
,
2
,
8
,
2
,
9
,
10
};
System.out.println(maxSum(
3
, a));
}
public
static
int
maxSum(
int
n,
int
[] a) {
int
sum =
0
;
for
(
int
i =
0
; i < a.length - n +
1
; i++) {
int
thissum =
0
;
for
(
int
v =
0
; v < n; v++) {
System.out.println(v +
"--"
+ i);
thissum += a[v + i];
}
System.out.println(
"---------------------------"
+ thissum);
if
(thissum > sum)
sum = thissum;
}
return
sum;
}
|
0--0
1--0
2--0
---------------------------22
0--1
1--1
2--1
---------------------------18
0--2
1--2
2--2
---------------------------12
0--3
1--3
2--3
---------------------------19
0--4
1--4
2--4
---------------------------21
22
本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/824843
