爷爷总是摸宝宝的小鸡鸡，怎么办呀？ (转载)# Joke - 肚皮舞运动
K*i
1 楼
如果准备不充分，经典题也会翻船的。我先贡献一个。
经典的数组求连续元素的最大和(Kadane算法)，面试官是老印。
我当然很快就写出那个标准的O(n)解法，但这个解法在所有数都为负数的情况下返回0
。老印随后要求所有数都为负数的情况返回最大的那个负数，我马上给了如下方法：
// step 1, 判断是否全部是负数，如果是，设置flag
for (...)
{
}
// step 2, 如果flag为false, 最初的解法
for (...)
{
}
// step 3, 如果flag为true, 遍历寻找最大的负数
for (...)
{
}
虽然我和他说了，这个三次循环是并列的，整体复杂度其实还是O(n)的。但老印显然非
常不满，问我能否减少为一个循环。我思考了一下，又给出方案如下，
在最初的解法的一次循环里头增加一些操作
bool all_neg = true;
for (...)
{
largest_sum还是用最初的解法更新
用一个变量largest_neg keep当前最大的负数
如果有非负的数, all_neg = false
}
if (all_neg)
return largest_neg;
else
return largest_sum;
老印说OK，然后就让我问问题了。最后的结果当然是被拒了。
某天翻看编程珠玑，这题出现的那章的习题里头提到更好的方法
最初的解法，设置largest_sum初值为0, 所以对全负数的情况返回0
只需要设置largest_sum为负无穷大，或者设置largest_sum为数组的第一个元素，最初
的解法就对全负数的情况返回最大的那个负数了。
我看过后才恍然大悟，这个才是老印要的答案，我的最初方案在他看来愚蠢到家，第二
个方案好些，但在他看来还是愚蠢，所以他拒我没商量。
经典的数组求连续元素的最大和(Kadane算法)，面试官是老印。
我当然很快就写出那个标准的O(n)解法，但这个解法在所有数都为负数的情况下返回0
。老印随后要求所有数都为负数的情况返回最大的那个负数，我马上给了如下方法：
// step 1, 判断是否全部是负数，如果是，设置flag
for (...)
{
}
// step 2, 如果flag为false, 最初的解法
for (...)
{
}
// step 3, 如果flag为true, 遍历寻找最大的负数
for (...)
{
}
虽然我和他说了，这个三次循环是并列的，整体复杂度其实还是O(n)的。但老印显然非
常不满，问我能否减少为一个循环。我思考了一下，又给出方案如下，
在最初的解法的一次循环里头增加一些操作
bool all_neg = true;
for (...)
{
largest_sum还是用最初的解法更新
用一个变量largest_neg keep当前最大的负数
如果有非负的数, all_neg = false
}
if (all_neg)
return largest_neg;
else
return largest_sum;
老印说OK，然后就让我问问题了。最后的结果当然是被拒了。
某天翻看编程珠玑，这题出现的那章的习题里头提到更好的方法
最初的解法，设置largest_sum初值为0, 所以对全负数的情况返回0
只需要设置largest_sum为负无穷大，或者设置largest_sum为数组的第一个元素，最初
的解法就对全负数的情况返回最大的那个负数了。
我看过后才恍然大悟，这个才是老印要的答案，我的最初方案在他看来愚蠢到家，第二
个方案好些，但在他看来还是愚蠢，所以他拒我没商量。
