递推关系
对于数组A[]={1，2，3，-4，-3，2，1},
如果有一个函数endsum(j),求出以位置j为终止点的最大子段和,则满足
if(endsum(j-1)>0)
endsum(j)=endsum(j-1)+A[j]
else
endsum(j)=A[j] 因为此时A[j]前面的元素只能降低和
上述递推关系是针对endsum
而最大子段和maxsum= max(endsum(0),endsum(1),...endsum(N-1))
测试说明
平台会对你编写的代码进行测试：
输入两行，第一行代表数组长度n，第二行是n个元素，假设n<10000
测试输入：
7 1 2 3 -4 -3 2 1
预期输出：
6
解析：文章来源：https://www.toymoban.com/news/detail-436222.html
计算一段的值，如果这一段的值大于0，则遍历后一个值时可以直接加上，因为加上一定大于当前遍历的值，若这一段值小于0，那么直接更新段值，因为前面的值加上一定会变小，所以直接抛弃，在每次更新时都与最大值max进行比较，若大于max则更新，最后返回max即可。文章来源地址https://www.toymoban.com/news/detail-436222.html
# include<stdio.h>
int main(){
int n;
scanf("%d", &n);
int a[n]={0};
for(int i = 0;i<n;i++){
scanf("%d", &a[i]);
}
int max = 0; # 最大值
int tem = 0; # 段值
for(int i=0;i<n;i++){
if(tem>0) # 前面一段值大于0
tem+=a[i];
else{ # 前面一段值小于0
tem=a[i]; # 抛弃前面的段值，更新段值
}
if(tem>max){ # 更新最大值
max=tem;
}
}
printf("%d", max);
return 0;
}到了这里，关于最大字段和（动态规划，C语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
