沧州网站建设 凯航,网站提升收录,wordpress用户组设置,山西网络营销外包给定N个整数的序列{ A1, A2, …, AN}#xff0c;其中可能有正数也可能有负数#xff0c;找出其中连续的一个子数列#xff08;不允许空序列#xff09;#xff0c;使它们的和尽可能大#xff0c;如果是负数#xff0c;则返回0。使用下列函数#xff0c;完成分治法求最大… 给定N个整数的序列{ A1, A2, …, AN}其中可能有正数也可能有负数找出其中连续的一个子数列不允许空序列使它们的和尽可能大如果是负数则返回0。使用下列函数完成分治法求最大子列和。 这是自己大一暑假写的逐次遍历的方法以下是分而治之的方法 题目如标题题目用到了分而治之的算法思想以下是分而治之的定义 “分而治之”Divide andConquer 是一种算法设计思想它将一个大问题分解成相互独立且相似的子问题然后递归地解决这些子问题最后将它们的解合并起来得到原问题的解。这种策略通常包括三个步骤 分解Divide 将原问题分解为若干个规模较小且相互独立的子问题。 解决Conquer 递归地解决这些子问题。如果子问题足够小可以直接求解。 合并Combine 将子问题的解合并起来形成原问题的解。 分而治之的思想常常应用在解决复杂问题的过程中它可以提高算法的效率。一些著名的算法如归并排序、快速排序、二分查找等都是采用了分而治之的策略。这种思想在许多计算机科学和算法领域都有广泛的应用。此题目就是用了分而治之中的二分法改善了题目的时间复杂度 这是自己大一暑假写的逐次遍历的方法
时间复杂度是O(n²)
#includestdio.h
#define MAX 100000
int main()
{int i,j,n,maxSum,tempSum,a[MAX];//定义数组大小的新方法即通过宏定义 scanf(%d,n);for(i0;in;i){scanf(%d,a[i]);}maxSum0;for(i0;in;i){tempSum0;//保证每个初始值为0 for(ji;jn;j)//循环不止有计数功能有数组时一定要注意下标 {tempSuma[j];if(tempSummaxSum)//核心问题可以算一步判断一步 maxSumtempSum;}}printf(%d,maxSum); }以下是分而治之的方法 T ( N ) O( N log N )
int MaxSum(int a[],int left,int right);
int threeOfMax(int a1,int a2,int a3);
int centerMaxSum(int a[],int left,int right);c #includestdio.h
#define N 50
int MaxSum(int a[],int left,int right);
int centerMaxSum(int a[],int left,int right);
int threeOfMax(int a1,int a2,int a3);
int main(){int n;int a[N];printf(请设置数组位数n\n);scanf(%d,n);printf(请输入数值\n);for(int i 0;in;i){scanf(%d,a[i]);}int left0;int rightn-1; int maxSubSum MaxSum(a,left,right);printf(最大子序列的和为:%d\n,maxSubSum);return 0;
} int MaxSum(int a[],int left,int right){int a1,a2,a3,i;int MaxLeftSum, MaxRightSum; //存放左右子问题的解int MaxLeftBorderSum, MaxRightBorderSum; //存放跨分界线的结果int LeftBorderSum, RightBorderSum;// 递归终止条件 直到分到最后一个元素 if(leftright){if( a[left] 0 )return a[left];elsereturn 0;}int mid (leftright)/2;// 划分左边a1 MaxSum(a,left,mid);// 划分右边a2 MaxSum(a,mid1,right);// 求解s3 MaxLeftBorderSum 0;LeftBorderSum 0;for( imid; ileft; i-- ) //从中线向左扫描{LeftBorderSum a[i];if( LeftBorderSum MaxLeftBorderSum )MaxLeftBorderSum LeftBorderSum;} //左边扫描结束MaxRightBorderSum 0;RightBorderSum 0;for( imid1; iright; i ) //从中线向右扫描{RightBorderSum a[i];if( RightBorderSum MaxRightBorderSum )MaxRightBorderSum RightBorderSum;} //右边扫描结束 a3 centerMaxSum(a,left,right);;//下面返回治的结果return threeOfMax( MaxLeftSum, MaxRightSum, MaxLeftBorderSum MaxRightBorderSum );}
// 求解s3
int centerMaxSum(int a[],int left,int right){int leftSum 0;int rightSum 0;int templeftSum 0;int temprightSum 0;int mid(leftright)/2;for(int i mid;ileft;i--){templeftSum templeftSuma[i];if(templeftSumleftSum)leftSumtempleftSum; }for(int j mid1;jright;j){temprightSum temprightSuma[j];if(temprightSumrightSum)rightSumtemprightSum;}return leftSumrightSum;
}// 求解最大的子列和
int threeOfMax(int a1,int a2,int a3){int maxSum a1a2?a1:a2;return maxSuma3?maxSum:a3;
}摘自
