int max_sub(int a[],int size)
{
int i,j,v,max=a[0];
for(i=0;i { v=0; for(j=i;j { v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1] if(v>max) max=v; } } return max; }那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现： int max_sub2(int a[], int size) { int i,max=0,temp_sum=0; for(i=0;i { 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.