一.

7-1 数字三角形 （30 分）

给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。

算法思想：通a[i][j]来表示该位置的最长路径，自底向上的计算比较，最后返回a[0][0],即整个数组的最大路径

代码实现：

#include
        
         #include
         
          int a[150][150];int fun(int b[][150],int n,int i,int j){	if(i==n-1) return b[i][j];	if(a[i][j]>=0)return a[i][j];			if(	b[i][j]+fun(b,n,i+1,j)>b[i][j]+fun(b,n,i+1,j+1))		return a[i][j]=b[i][j]+fun(b,n,i+1,j);		else return a[i][j]=b[i][j]+fun(b,n,i+1,j+1);  }int main(){	//freopen("in.txt","r",stdin);	//freopen("out.txt","w",stdout);	memset(a,-1,sizeof(a));	int n;	int b[150][150];	 int i,j; 	scanf("%d",&n);	for(i=0;i
         
        

　　时间复杂度o（n*n）

二.

7-2 最大子段和 （40 分）

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

算法分析：通过b接收a当前位置的最大字段和，最后返回sum

代码实现：

#include 
           
            using namespace std;int MaxSum(int n,int a[]){	int sum=0,b=0;	for(int i=1;i<=n;i++)    {    	if(b>0) b+=a[i];    	else b=a[i];    	if(b>sum) sum=b;    }    return sum;}int main(){	int n,a[10001];	cin>>n;	for(int i=1;i<=n;i++)	cin>>a[i];	cout<
           

　　时间复杂度o(n),空间复杂度（n）

三.结对编程感悟

此次实践中，我们对问题有不断地思考和分析，最后得到一致的思路和结果。两人配合的高效率也体现其中。