{
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
else if(temp_sum<0)
temp_sum=0;
}
return max;
}
在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum 将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。
google面试试题汇总（转）
笔试题目：9道单选+3道问答” W, B2 n2 A8 m2 P+ T) t
时间：100分钟/ A) Z; e4 * l( d9 Y, v’ K
我做的是B卷。3 N1 B; C6 j& T# L/ N) r
单选题：
& ^: g i/ T g” n2 p3 {1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
! ; v6 f/ Y’ }9 P2，不记得了。。也是不需要思考的题目。。
2 ]# P Z’ p! u: N3，大概是如下的函数：& `; n7 E7 B2 A n- N7 h) Y
int someFunc(int x){* ]7 D# _; F# m. b
if (x == 0)
8 S5 {, T9 ~4 ~8 L2 Q2 G3 c! I return 0;( h5 ]5 A& v: { x
else” l8 _% U) R4 L* l
return x + someFunc(x – 1);
2 t1 k- d# D” \/ k7 Q1 E( M3 ]}6 H- K c5 W9 W) J6 Y8
问这个计算的是什么。。。% U! m: L/ n, s6 z8 s$ B$ S8 N
4，不记得了。。不需要思考吧。。
o7 {3 q, e’ y+ k2 C. ~’ B# N5，不记得了。。不需要思考吧。。
+ i# F8 y T# T+ R& x; L6，参见2，4，5。。- a1 d! b; }4 w% {2 Y9 @
7，似乎需要思考一下。。 u5 F c; W, l0 S
8，问链表结构和数组相比的优势不包括哪项，
$ Q2 U7 C/ v5 `- z. i/ l包括：1 S8 ]. C’ Z# C” G” c
插入的时间/ q: x. R2 f6 w’ |: x2 H9 j8 D4 y$ R
删除的时间1 S/ \’ S2 b- T% U! I+ J7 I
存储空间2 V8 L& ~; s8 y6 O% T2 y
剩下两个不记得了。。
” ]- `, P4 q! `6 ]2 k9，如下函数：1 z8 T3 U# I- C( v. R$ x# N+ u% s
T(x) = 1 (x <= 1)
8 s5 i; R: G+ V& S# A* aT(n) = 25 T(n/5) + n^2
# \7 p8 L* J- t问T(n)随n的增长。
. U# 6 F0 ^* W选项大概是这样的：% Q+ N’ U- `1 I. I( z: {* l9 Q, y
O(n^2)，O(n^2logn)等等的。。
/ C$ _; R Q5 x) n1 ^ O” f8 v5 L, d( g5 ]
问答：1 J- M$ I. k% x+ W+ H/ g
1，写两个N*N的矩阵的乘法，给出了C的格式，你可以选择你喜欢的语言去写。。0 s: v” H- {( Y- Q$ ]5 O2 y
int* multi(int* a1, int* a2, int N){; ] s5 H2 a/ w) W5 B1 X
}! [* e: q. v; P" V) w7 S; Q+ H$ _
2，寻找一个单向链表的中项，如果存在两个则返回前一个。给出了C的格式，同样你可
) a' l& R5 K2 h1 q0 F7 R以选择。。。。
7 `' g$ j( V+ ] zstruct {0 W” _! x/ H8 }3 G; {4 i4 d
Node* next;
$ T5 @# y; N3 I h% E } int value;
) I+ z’ ~4 F1 @: H4 a} Node;2 U; p1 U, \/ G9 l7 R/ C; `. e
Node* someFunc(Node* head){
5 s* P+ X1 }7 N, }}
. p6 J! l$ s4 H0 o& }. E3，给一个长度为n的整数数组，只允许用乘法不允许用除法，计算任意(n-1)个数的组合
+ c% {$ E% g8 v: F, r( c2 \& |2 z乘积中最大的一组。。。写出算法的时空复杂度。$ r4 A* _/ l0
Google笔试题2006
选择题
. A6 z* e9 `& Z$ z x- Q/ N& n# _( E$ p& R ]9 s0 P% 5 w
1. 把一个无符号16位整数a的最高为置为1
2. Fibonacci,求f(4）使用递归调用f(1)的次数f(n) = f(n-1)+f(n-2)
3 D0 B1 Y3 F7 X( B4 l: Y5 p8 R# B( Zf(0)=0, f(1)=1
, U& b1 B0 d7 x; e. d# h% Ra.5 b.4 c. 3 d. 4以上
! I’ u2 v: y# f’ t N3 k(
‘ W& |2 O$ w+ m& K1 B, _3. if (xAS{print “1″}. ]% i6 E’ M8 L2 K
S->AB{print “2″}
9 ~& c2 p. D* D+ lA->a{print “3″}’ X/ h’ O” y3 p3 k. h’ J’ c
B->bC{print “4″}+ t6 {( e’ j2 X7 Y; q6 y! W
B->dB{print “5″}
‘ v# E6 R6 S1 _! hC->c{print “6″}
3 D& N2 c2 k9 k
0 C# x6 ]# @0 m’ X% w8 |- P6. 有关哈希表正确的说法（不定项）3 L7 j’ N. b9 f. z9 A
a.哈希表的效率和哈希函数。。。。相关3 h* O& P9 j- Z’ N
b.哈希表的解决冲突方法慢，回影响哈希表效率’ r2 r( {) y0 @* r7 U ]
c.使用链表哈希可使内存紧凑
2 h- Y7 l6 i) l% G$ s, m. f$ 9 X, g0 `$ V8 z6 m. Z: H
7. 一种无饥饿调度方法是：
9 L+ j8 O! V) `) x; Wa. 轮叫调度
( ^9 }! M& R6 @1 c0 Yb.
! s2 ], x” K: X/ \: pc. 最短使用时间
/ m! F: }* {1 H4 X% td. 最新队列. A; e- m9 U5 n9 t( Z9 S9 k
& e, Q ^# e! u1 n: C8. 下列排序方法最差情况时间复杂度为O(n^2)的是：
& z5 u) x/ z, Q0 `5 O; ma. 插入# R9 V* x7 \2 i
b. 归并
2 a Z! x8 o$ `. \c. 冒泡
! Y* I. Q6 z f% S! D6 t( xd.