给定N个整数的序列{ A1, A2, …, AN}，其中可能有正数也可能有负数，找出其中连续的一个子数列（不允许空序列），使它们的和尽可能大，如果是负数，则返回0。使用下列函数，完成分治法求最大子列和。
- 这是自己大一暑假写的逐次遍历的方法
- 以下是分而治之的方法
题目如标题，题目用到了分而治之的算法思想，以下是分而治之的定义：
“分而治之”（Divide andConquer）
是一种算法设计思想，它将一个大问题分解成相互独立且相似的子问题，然后递归地解决这些子问题，最后将它们的解合并起来得到原问题的解。这种策略通常包括三个步骤：分解（Divide）： 将原问题分解为若干个规模较小且相互独立的子问题。
解决（Conquer）： 递归地解决这些子问题。如果子问题足够小，可以直接求解。
合并（Combine）： 将子问题的解合并起来，形成原问题的解。
分而治之的思想常常应用在解决复杂问题的过程中，它可以提高算法的效率。一些著名的算法，如归并排序、快速排序、二分查找等，都是采用了分而治之的策略。这种思想在许多计算机科学和算法领域都有广泛的应用。此题目就是用了分而治之中的二分法，改善了题目的时间复杂度
这是自己大一暑假写的逐次遍历的方法
时间复杂度是O(n²)
#include<stdio.h>
#define MAX 100000
int main()
{int i,j,n,maxSum,tempSum,a[MAX];//定义数组大小的新方法，即通过宏定义 scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);}maxSum=0;for(i=0;i<n;i++){tempSum=0;//保证每个初始值为0 for(j=i;j<n;j++)//循环不止有计数功能，有数组时，一定要注意下标 {tempSum+=a[j];if(tempSum>maxSum)//核心问题：可以算一步，判断一步 maxSum=tempSum;}}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
#include<stdio.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;i<n;i++){scanf("%d",&a[i]);}int left=0;int right=n-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(left==right){if( a[left] > 0 )return a[left];elsereturn 0;}int mid = (left+right)/2;// 划分左边a1 = MaxSum(a,left,mid);// 划分右边a2 = MaxSum(a,mid+1,right);// 求解s3 MaxLeftBorderSum = 0;LeftBorderSum = 0;for( i=mid; i>=left; i-- ) //从中线向左扫描{LeftBorderSum += a[i];if( LeftBorderSum > MaxLeftBorderSum )MaxLeftBorderSum = LeftBorderSum;} //左边扫描结束MaxRightBorderSum = 0;RightBorderSum = 0;for( i=mid+1; i<=right; 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=(left+right)/2;for(int i = mid;i>=left;i--){templeftSum = templeftSum+a[i];if(templeftSum>leftSum)leftSum=templeftSum; }for(int j = mid+1;j<=right;j++){temprightSum = temprightSum+a[j];if(temprightSum>rightSum)rightSum=temprightSum;}return leftSum+rightSum;
}// 求解最大的子列和
int threeOfMax(int a1,int a2,int a3){int maxSum = a1>a2?a1:a2;return maxSum>a3?maxSum:a3;
}
摘自
