问题描述
int
MaxSubsequenceSum（const int A []，int N）
{
int ThisSum，MaxSum，j;
ThisSum = MaxSum = 0;
for（j = 0; j< N; j ++）
{
ThisSum + = A [j];
if（ThisSum MaxSum）
{
MaxSum = ThisSum;
}
否则如果（ThisSum< 0）
{
ThisSum = 0;
}
}
返回MaxSum;
}
我认为上面的代码是获得MaxSubsequenceSum的好选择
T（n）= O（n），但如果数组A包含完整的负值，则
函数将返回零。
我想添加一个部件代码来测试A数组值，但是这将会破坏代码恩典，然后代码会变得难看（我想）。
你有解决问题的好方法吗？
谢谢。
将MaxSum和ThisSum初始化为[0]，使循环以
j = 1开始，并删除else分支。 />
BTW，通常所有大写标识符都用于宏，使用
小写可能会让那些习惯于这个
约定的人感到困惑。
-
Army1987（将NOSPAM替换为电子邮件）
汉堡包总比没有好。
没有什么比永恒的幸福更好了。
因此，汉堡包比永恒的幸福更好。
将MaxSum和ThisSum初始化为[0]，使循环以
j = 1开始，并删除else分支。
我认为打破它。
-
Ben。
将MaxSum和ThisSum初始化为[0]，使循环以
j = 1开始，并删除else分支。
我认为打破它。
....但考虑一下，如果你的意思是将MaxSum设置为[0]而
ThisSum为0，你可以是的。它看起来像OP
想要的那样。要小心，因为，与Knuth不同，我只测试了这个，而不是
证明了它！
-
Ben。
int
MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for (j = 0; j < N; j++)
{
ThisSum += A[j];
if (ThisSum MaxSum)
{
MaxSum = ThisSum;
}
else if (ThisSum < 0)
{
ThisSum = 0;
}
}
return MaxSum;
}
I think the above code is a good choice to obtain MaxSubsequenceSum
T(n) = O(n), but If the array A contain full negative value, the
function will return zero.
I think to add a part code to test the A array value, but this will
destroy code grace, and then the code will become ugly(I think).
Do you have a good method to resolve the problem?
Thank you.
Initialize MaxSum and ThisSum to a[0], make the loop start with
j=1, and remove the else branch.
BTW, usually all-caps identifiers are used for macros, using
lowercase could be less confusing for people used to this
convention.
--
Army1987 (Replace "NOSPAM" with "email")
A hamburger is better than nothing.
Nothing is better than eternal happiness.
Therefore, a hamburger is better than eternal happiness.
Initialize MaxSum and ThisSum to a[0], make the loop start with
j=1, and remove the else branch.
I think that breaks it.
--
Ben.
Initialize MaxSum and ThisSum to a[0], make the loop start with
j=1, and remove the else branch.
I think that breaks it.
.... but thinking about it, if you meant setting MaxSum to a[0] and
ThisSum to 0, you may be right. It looks like that does what the OP
wants. Beware because, Unlike Knuth, I have only tested this, not
proved it!
--
Ben.
这篇关于是个bug吗？关于MaxSubsequenceSum（）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！