基本题二：最大字段和问题
一、实验目的与要求
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