编译环境：Dev-C++
分别用暴力枚举，优化枚举，递归分治和动态规划的方法解决最大字段和问题。
最大字段和问题描述：
给定n个整数（可能为负整数）组成的序列a1,a2,…,an，求该序列连续的子序列和的最大值。 如果该子段的所有元素和是负整数时定义其最大子段和为0。
最大子段和问题的形式化描述：
算法思想
（1）暴力枚举法思想：
用一个三重循环，i和j从1到n分别表示每一次加法加数和最后一个被加数的下标，k从i到j用来做a[i]到a[j]求和，每次循环加和定义一个当前最大子段和thissum和sum比较替换；
（2）优化枚举法思想：
在暴力枚举下，我们很容易想到可以把k这一重循环省略，避免了重复加和，例如：要求sum[3,8]，只需要在sum[3,7]的基础上加a[8],而不需要再从a[0]加到a[8]，从而提高效率。
（3）分治法思想：
将原数组a[left,right]分为长度相同的两段子数组a[left,mid]和a[mid+1,right]；
然后利用递归分别求解左半段和又半段的最大子段和；
这个时候分成三种情况：
第一种情况是：最大子段和为左半段最大字段和；
第二种情况是：最大子段和为右半段最大字段和；
第三种情况是：跨中间的最大字段和；求解思想见下图：
最后把三种情况的最大子段和做比较就可以得出最大子段和。
（4）动态规划法：
之所以用到了动态规划的思想，是因为问题具有最小子结构性质，而且子问题之间有所重复，原问题的最优解可以由此问题从底向上推导出来
定义一个f数组复制a数组，f[i]表示以a[i]为结束的子数组最大和，f[i]一定是包涵a[i]的，所以如果前面的子问题最优解是小于0，那么包涵以a[i]为结尾的最大字段和，就是它自己，而如果前面的子问题最优解大于或者等于0，则把a[i]加上f[i-1]就是他的最大子段和；
算法调试过程及输入输出结果：
测试用例：
Input:
7
1 -5 2 4 5 -1 7
Output:
17
2 4 5 -1 7
文章来源：https://www.toymoban.com/news/detail-407571.html
可以看到，通过一步步简化，时间复杂度从O(n^3)到O(n^2)到O(nlogn)再到O(n)，时间复杂度不断改进，这就是算法的魅力！ 文章来源地址https://www.toymoban.com/news/detail-407571.html
源代码：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
/*测试用例：
Input:
7
1 -5 2 4 5 -1 7
Output:
17
2 4 5 -1 7
*/
//暴力枚举法
int MaxSubSum_Violent(int *a,int n,int& besti,int& bestj){
int sum=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int thissum=0;
for(int k=i;k<=j;k++){
thissum+=a[k];
}
if(thissum>sum){
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
}
//优化枚举法
int MaxSubSum_Optimized(int *a,int n,int &besti,int &bestj){
int sum=0;
for(int i=0;i<n;i++){
int thissum=0;
for(int j=i;j<n;j++){
thissum+=a[j];
if(thissum>sum){
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
}
//分治法
int CrossSubArray(int *a,int left,int mid,int right){
int leftsumMax=0,rightsumMax=0,temp=0;;
for(int i=mid;i>=left;i--){
temp+=a[i];
if(temp>=leftsumMax){
leftsumMax=temp;
}
}
temp=0;
for(int j=mid+1;j<=right;j++){
temp+=a[j];
if(temp>=rightsumMax){
rightsumMax=temp;
}
}
int crosssum=leftsumMax+rightsumMax;
return crosssum;
}
int MaxSubSum_DivideConquer(int *a,int left,int right){
int sum=0;
if(left==right){
sum=a[left];
}else{
int mid=(left+right)/2;
int leftsum=MaxSubSum_DivideConquer(a,left,mid);
int rightsum=MaxSubSum_DivideConquer(a,mid+1,right);
int crosssum=CrossSubArray(a,left,mid,right);
if(leftsum>=rightsum&&leftsum>=crosssum){
sum=leftsum;
}else if(rightsum>=leftsum&&rightsum>=crosssum){
sum=rightsum;
}else if(crosssum>=rightsum&&crosssum>=leftsum){
sum=crosssum;
}
}
return sum;
}
//动态规划
int MaxSubSum_DynamicProgram(int *a,int n){
int Max_sum=0;
int *f=(int *)malloc(sizeof(int)*(n+1));
for(int i=0;i<n;i++){
f[i]=a[i];
}
for(int i=1;i<=n;i++){
if(f[i-1]+a[i]>=a[i]) f[i]=f[i-1]+a[i];
if(f[i-1]+a[i]<a[i]) f[i]=a[i];
if(f[i]>=Max_sum) Max_sum=f[i];
}
// for(int i=1;i<=n;i++){
// if(f[i-1]>=0) f[i]=f[i-1]+a[i];
// if(f[i-1]<0) f[i]=a[i];
// if(f[i]>=Max_sum) Max_sum=f[i];
// }
return Max_sum;
}
int main(){
int n=0;
printf("请输入原数组的长度：");
scanf("%d",&n);
int *a=(int*)malloc(sizeof(int)*(n+1));
if(!a) exit(-2);
puts("请输入原数组：");
for(int i=0;i<n;i++){
scanf("%d",a+i);
}
int besti,bestj;
puts("使用暴力枚举法的结果是");
printf("最大子段和为：%d\n",MaxSubSum_Violent(a,n,besti,bestj));
puts("对应的子数组为：");
for(int i=besti;i<=bestj;i++){
printf("%d ",a[i]);
}
putchar('\n');
puts("--------------------------------");
puts("使用优化枚举法的结果是");
printf("最大子段和为：%d\n",MaxSubSum_Optimized(a,n,besti,bestj));
puts("对应的子数组为：");
for(int i=besti;i<=bestj;i++){
printf("%d ",a[i]);
}
putchar('\n');
puts("--------------------------------");
puts("使用分治法的结果是");
printf("最大子段和为：%d\n",MaxSubSum_DivideConquer(a,0,n));
puts("--------------------------------");
puts("使用动态规划法的结果是");
printf("最大子段和为：%d\n",MaxSubSum_DynamicProgram(a,n));
}
到了这里，关于最大子段和问题算法设计（C语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
