一、要求:
输入一个二维的整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个二维子数组,每个子数组都有一个和。
求所有子数组的和的最大值。
二、设计思想:
如果数组首尾相连,那么每一个元素都可以当成是开头即从A[n]开始,到A[n-1]结束,这样的话,就相当用剪子在一开始的数组中的元素的前一位剪开。这样的话,可以建立新的三个数组,前两个数组分别盛放剪开的两部分,第三个数组则是负责把前两个数组按顺序存放起来。前两个数组的长度之和等于第三个数组长度。这样便组成了新的数组。再按照以前计算条形数组的方法计算即可。
三、程序代码:
#include <iostream>
#include<ctime>#define Num 10000using namespace std; int DTGH_Sum(int a[],int n) //动态规划法求子段和函数{ int sum = 0; int *b = (int *) malloc(n * sizeof(int)); //动态为数组分配空间 b[0] = a[0]; for(int i = 1; i < n; i++) { if(b[i-1] > 0) b[i] = b[i - 1] + a[i]; else b[i] = a[i]; } for(int j = 0; j < n; j++) { if(b[j] > sum) sum = b[j]; } delete []b; //释放内存 return sum;}int main() { int temp,b; int sum=0; int i; int a1,a2; int a[Num]; int length=0; while (length==NULL||length == 0)//如果数组长度为空或零则请重新输入 { cout<<"请输入数组长度:"; cin>>length; } cout<<"生成随机数组: "<<endl; srand((unsigned)time(NULL)); for(i=0;i<length;i++)//产生随机序列 { if(rand()%2==0) { a[i]=rand()%50; } else { a[i]=(-1)*rand()%50; } cout<<a[i]<<" "; } cout<<endl; cout<<"此首尾相连的数组中最大子数组的和有以下几种可能:"<<endl; cout<<"第1种排列方式:"<<endl; for( i=0;i<length;i++) { cout<<a[i]<<" "; } cout<<"最大子数组和为:"<<DTGH_Sum(a,length)<<endl; a1=DTGH_Sum(a,length); for(b=1;b<length;b++) { temp=a[0]; for(i=1;i<=length;i++) { a[i-1]=a[i]; //将第一个数变为最后一个数 } a[length-1]=temp; cout<<"第"<<b+1<<"种排列方式:"<<endl; for( i=0;i<length;i++) { cout<<a[i]<<" "; } cout<<"最大子数组和为:"<<DTGH_Sum(a,length)<<endl; if(DTGH_Sum(a,length)>=sum) { sum=DTGH_Sum(a,length); } } a2=sum; cout<<endl; if(a1>=a2) { cout<<"综上,最大的子数组和为:"<<a1<<endl; } else { cout<<"综上,最大的子数组和为:"<<a2<<endl; } return 0; }
四、运行结果:
五、照片
单人从网上学习,无。