动态规划算法求最大子段和有关问题

分类: IT文章 • 2022-05-21 15:33:22

动态规划算法求最大子段和问题
给定由N个整数(可能有负整数)组成的序列a1,a2,...,an ,求该序列形如ai+ai+1+...+aj的子段和的最大值。

当所有整数均为负整数时,定义其最大子段和为0

int MaxSum(int *a, int n)
{ int sum=0,b=0;
for( int j=1; j<=n; j++)
{ if ( b>0) b+=a[j]; else b=a[j];
if(b>sum) sum= b;}
return sum;
}

时间复杂度为O(n)