动态规划 - 最大子段和
问题描述
给定 n 个整数组成的序列 a[1],a[2],a[3],……,a[n] ,求该序列如 a[i],a[i+1],a[i+2],……,a[j] 的连续子段和的最大值。
例如,在序列 -2,11,-4,13,-5,-2 中,最大子段和为 20 。
分析
记 b[j]=max(a[i]+a[i+1]+……+a[j]) ,其中 1<=i<=n,1<=j<=n ,则所求最大子段和为 max=max(b[j]),1<=j<=n 。
显然,该问题满足 无后效性 。在计算 b[j] 时,我们需要考虑 b[j-1] ,即考虑之前序列的最大子段和的正负情况:
当 b[j-1]>0 时,有 b[j]=b[j-1]+a[j] ;
当 b[j-1]<=0 时,有 b[j]=a[j] 。
实现
#include<stdio.h>
int main(void){
int count,a[]; //定义测试数组以及其大小
int b[]; //定义子段和数组
int max;//含 count 项序列的最大子段和
scanf("%d",&count);
for(int i=;i<count;i++){
scanf("%d",&a[i]);
}
b[]=a[];
max=b[];
for(int i=;i<count;i++){
if(b[i-]>)
b[i]=b[i-]+a[i];
else
b[i]=a[i];
if(b[i]>max)
max=b[i];
}
printf("%d",max);
return ;
}
#include<stdio.h>
int max(int num1,int num2);
int maxSum(int data[],int count);
int main(void){
int count,data[];
scanf("%d",&count);
for(int i=;i<count;i++){
scanf("%d",&data[i]);
}
printf("%d",maxSum(data,count));
return ;
}
int max(int num1,int num2){
return num1<num2?num2:num1;
}
int maxSum(int data[],int count){
int currentSum=data[];
int ans=currentSum;
for(int i=;i<count;i++){
currentSum=max(currentSum+data[i],data[i]);
ans=max(ans,currentSum);
printf("%d",ans);
}
return ans;
}