求出一个整型数组的最大子集和
时间：2014-03-11 00:51:19
收藏：0
阅读：507
小组成员： 杨世超 李夏蕾
这是我们软件工程老师上课进行的结对小组实践题目，我们两个人商量了思路，和具体的解题过程
下面是我们的解题思路：
首先动态的输入数组元素
然后通过三层的for循环来进行遍历数组
第一层循环是数组的开始部分，第二层是数组子集的元素个数，第三层是求其相应的和，并与每一次的max相比较，保留最大值。
从每一个的开端一个一个遍历，先求出以a[0]开始的所有子集，再依次求出以a[i]开头的所有子集，并依此保留一次遍历的最大值，及其相应的长度，利用数组存储对应的最大值和长度，最后再进行比较，并输出最大值和数组最大子集。
在这个过程中，由于循环的利用导致有的时候循环的数目不对或者是初始化放错了地方等等，在此过程中，我们进行了一点一点的修改，利用单步跟踪调试，一点一点的看到底是哪里出错了，最终才完成了如下的模块：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
for(i=0;i<n;i++) { length=1; max=a[i]; for(j=1;j<=n-i;j++) { sum=0; for(k=i;k<i+j;k++) { sum=sum+a[k]; } if(max<=sum) { max=sum; length=j; } b[i]=max; c[i]=length; } } |
最后通过数组进行比较每一次的遍历最大值，然后求出最终的结果
程序源代码如下：
|
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
52
53
54
55
56 |
#include<iostream>#define N 100using
namespace std;int main(){ int
n,t; int
sum; int
i,k,j; int
a[N],b[N],c[N]; int
max; int
length; cout<<"请输入数组的个数:"<<endl; cin>>n; cout<<"请输入数组元素:"<<endl; for(i=0;i<n;i++) { cin>>a[i]; } for(i=0;i<n;i++) { length=1; max=a[i]; for(j=1;j<=n-i;j++) { sum=0; for(k=i;k<i+j;k++) { sum=sum+a[k]; } if(max<=sum) { max=sum; length=j; } b[i]=max; c[i]=length; } } max=b[0]; t=0; for(i=0;i<n;i++) { if(max<b[i]) { max=b[i]; t=i; } } cout<<"最大子数组和是:"; cout<<max<<endl; cout<<"子序列为"<<endl; for(i=t;i<t+c[t];i++) { cout<<a[i]<<endl; }} |
为了检测程序的性能，我们用了如下的一些数据：
（1）数组只有一个元素
（2）数组最大子集的开头有0
（3）数组最大子集的末尾有0
（4）数组元素有正有负
由于很多地方不一定能实现，所以在测试时我们进行了一系列的修改，让它能满足要求，比如说数组中前一个0不输出，后一个0不输出，等等问题，都进行了相应的修改
下面是我们测试结果截图：
原文：http://www.cnblogs.com/yangshichao/p/3592517.html
评论（0）