K*****k
发帖数: 430 | 1 那是四年以前的事了，一个MSFT失败的电面经历：
题目很简单，就是经典的数组求连续的子数组最大和，心中暗喜，很快搞定。
老印接着问，如果数组全是负数怎么办？我说这个方法返回0
老印说，如果要求返回最大的负数呢？
我说检查这个特殊情况单独处理，然后开始写代码
1）先写了第一个一重循环，判断是否全部是负数
2) 如果不全是负数，用先前的方法，第二个一重循环
3）如果全是负数，在用第三个一重循环找到最大的负数
老印说，这样写太麻烦了。我说是，但是三个并列的一重循环，结果还是O(N)的
老印说，你还有什么改进么？
我看了看说，可以在1）中就同时求得最大负数，这样就减少为两个一重循环
老印说，你还能改进么？
我想了想说，可以在2)那个循环中,keep最大的负数和判断是否全部是负数，这样就减
少为一个一重循环了。
老印说OK
电面后看了看编程珠玑的这题，在课后习题中有提到全部负数情况，只需要
一开始的时候不用max = 0; 而用max = -INF或者max = A[0]就可以处理全部负数的情
况。
老印肯定知道这个方法，但他没有说，而在心中暗笑我的愚蠢的拙劣代码。
果然N天后，被默拒了。 |
j*****8
发帖数: 3635 | 2 算法导论课后习题也有这题。。
【在 K*****k 的大作中提到】
: 那是四年以前的事了，一个MSFT失败的电面经历：
: 题目很简单，就是经典的数组求连续的子数组最大和，心中暗喜，很快搞定。
: 老印接着问，如果数组全是负数怎么办？我说这个方法返回0
: 老印说，如果要求返回最大的负数呢？
: 我说检查这个特殊情况单独处理，然后开始写代码
: 1）先写了第一个一重循环，判断是否全部是负数
: 2) 如果不全是负数，用先前的方法，第二个一重循环
: 3）如果全是负数，在用第三个一重循环找到最大的负数
: 老印说，这样写太麻烦了。我说是，但是三个并列的一重循环，结果还是O(N)的
: 老印说，你还有什么改进么？
|
A*****i
发帖数: 3587 | 3 我一直觉得这个题虽然挺简单但是有点儿DP的思想在里面 |
f**********t
发帖数: 1001 | 4 int res = INT_MIN;
int sum = 0;
for (size_t i = 0; i < A.size(); ++i) {
sum += A[i];
res = max(res, sum);
if (sum < 0) {
sum = 0;
}
}
【在 K*****k 的大作中提到】
: 那是四年以前的事了，一个MSFT失败的电面经历：
: 题目很简单，就是经典的数组求连续的子数组最大和，心中暗喜，很快搞定。
: 老印接着问，如果数组全是负数怎么办？我说这个方法返回0
: 老印说，如果要求返回最大的负数呢？
: 我说检查这个特殊情况单独处理，然后开始写代码
: 1）先写了第一个一重循环，判断是否全部是负数
: 2) 如果不全是负数，用先前的方法，第二个一重循环
: 3）如果全是负数，在用第三个一重循环找到最大的负数
: 老印说，这样写太麻烦了。我说是，但是三个并列的一重循环，结果还是O(N)的
: 老印说，你还有什么改进么？
|
H**********5
发帖数: 2012 | 5 这种题没什么水平，
完全是你事先看没看过，
看过了，立马就能答出来，
没看过，短时间内不一定能答得出来。 |
I*******g
发帖数: 7600 | 6 现在刷题也一样，
没有刷的题目被问到一样死。
【在 H**********5 的大作中提到】
: 这种题没什么水平，
: 完全是你事先看没看过，
: 看过了，立马就能答出来，
: 没看过，短时间内不一定能答得出来。
|
s*******m
发帖数: 228 | 7 有什么办法没
【在 I*******g 的大作中提到】
: 现在刷题也一样，
: 没有刷的题目被问到一样死。
|
A*****i
发帖数: 1420 | |
