编程之美扩展问题

1. 学的c++能看《编程之美》吗

可以的。
《编程之美——微软技术面试心得》收集了约60道算法和程序设计题目，这些题目大部分在近年的笔试，面试中出现过，或者是被微软员工热烈讨论过。作者试图从书中各种有趣的问题出发，引导读者发现问题，分析问题，解决问题，寻找更优的解法。
这本书里面主要涉及到的是各种算法的讨论，以及对程序设计思路的引导。对于任何语言的学习者都是有帮助的。其中大部分算法描述更是采用了C语言作为例子，所以，学习C++看编程之美是没有障碍的。
但是，由于这本书里面涉及到的一些算法比较困难，对于初学者来说会有些偏难，所以最好在C++有一定功底后再去阅读。

2. 计算机有哪些必读的经典书籍

计算机专业学习的过程中，大家学习了程序语言C/C++、数据结构、数据库、计算机组成原理、操作系统和计算机网络等基础课，但是还有许多经典书籍值得我们一读，阅读这些书籍不但对我们个人能力提升而且对个人应聘找工作都有很大的帮助。下面罗列出一些经典书籍供大家参考。
1. 程序语言方面
C语言作为最经典的语言，也是计算机专业最先学习的一门语言。首先推荐几本C语言经典书籍：
《C和指针》
《C缺陷与陷阱》
《C专家编程》
《C语言深度剖析》

Expert C Programming
其中《C专家编程》从C的历史、语言特性、声明、数组指针、链接、运行时内存等问题进行了细致的讲解和深入的分析，全书展示出很多优秀的编码技巧，特别适合有一点C语言基础的人观看。《C语言深度剖析》是国内写的一本书，重点讲解了C语言里的一些晦涩难度的问题。
C++语言经典书籍：
《C++ Primer 5th》
《Effective C++》
《深度探索C++对象模型》
《STL源码解析》

C++ Primer
以上几本是学好C++必读的书籍，《C++ Primer 5th》由浅入深全面的讲解了C++的语法与程序设计，是C++程序员必读的一本书，《深度探索C++对象模型》对C++运行原理作了一个很好的剖析，详细的讲解了对象内存模型以及调用运行的本质，对深入理解C++内部机制来说是一本非常好的书籍。计算机底层书籍：
《编码》
《编译原理》
《汇编语言》
《C++反汇编与逆向分析》
Code
《编码》深度形象的讲解了计算机的原理，看完此书后你会对计算机的工作原理有较深刻的理解，强烈推荐大家看一看。
2. 算法、数据结构相关
《算法导论》
《编程珠玑》
《编程之美》
《算法艺术与信息学竞赛》
《算法导论》是算法领域的圣经，这本书很厚并且理论知识较强，很难从头到尾认真的看一遍，大家可以选择性地看，当然能完整的看完就更好了。《编程珠玑》和《编程之美》这两本书也非常经典，里面注重的是解决问题的思路，看的时候要认真思考里面的问题。最后一本是关于ACM方面的书，如果自己能力足够强的话，看看这本书也还是挺不错的
LeetCode 中国
当然，这里不得不向大家推荐的就是 LeetCode 在线技术平台了，专注于做算法、学习、求职和计算机科学相关的内容，被誉为计算机界的刷题神器。目前，LeetCode 也已经进入中国，有自己的中文网站（ leetcode-cn ），不仅提供了 LeetCode 的全部服务，还有中英文题目对照和中文社区，总算可以愉快的刷题了。
3. 操作系统相关
《深入理解操作系统》
《linux内核完全注释》
《自己动手写操作系统》
《Windows内核原理与实现》
Linux内核完全注释
《Linux内核完全注释》一书选取了代码量不超过2万行的linux 0.11内核，对内核代码的每一个细节都作出了详细的讲解，麻雀虽小，五脏俱全，看完这本书对linux操作原理会有一个很深的理解，是国内一本非常优秀的书。
4. 软件开发、设计相关
《Head First 设计模式》
《设计模式-可复用面向对象软件的基础》
《重构与模式》
《代码大全》
《设计模式》（GOF）
Head First - 设计模式
设计模式在工作中重要性尤其突出，良好的软件设计对于后期的维护、扩展有着重要的作用，对于大型软件，首先要做的就是设计好整个软件架构，这也是整个软件开发过程中最难的一个环节。
5. 数据库
《数据库系统概念》
《数据库系统实现》
《Mysql技术内幕：sql编程》
《MySQL技术内幕: InnoDB存储引擎》

3. 求不连续子数组最大和的值

这是一道典型的动态规划问题，书中循序渐进地通过分析给出了一个时间复杂度为O(N)空间复杂度为O(1)的最优解。我在面试时碰到了这道题的一道有趣变体，即同样给定一个数组，写一个在其中找出不连续子数组和的最大值，也就是说子数组里的任意相邻的两个元素，在原数组里都必须是不相邻的才行。同样以数组{1, -2, 3, 5, -1, 2}为例，则和最大的不连续子数组是{1, 5, 2}，函数返回值是8。
显然，最直接的思路我们可以采用穷举法，对于此类寻找符合条件的子数组的问题，无非就是对原数组上每位元素是否属于子数组做一次遍历判断。由于每位元素都有属于和不属于子数组两种可能性，那么穷举的时间复杂度为O(2^N)。即使考虑“不连续”这个限制条件，即某位元素被选中属于子数组后，则其相邻元素就一定不能被选中，也对时间复杂度的数量级不会有太多影响。因此很明显，这绝对是个愚蠢的答案……
从《编程之美》一题中得到启发，我们是不是也可以用动态规划的方法来解这道题呢？假设从原数组a第i位开始的最大不连续子数组和为m[ i ]，那么它的值有两种可能，一种是当前元素a[ i ]与隔一位上子问题解m[ i+2 ]之和（由不连续性质决定），另一种是不包含当前元素而直接等于前一位上子问题解m[ i+1 ]，那么我们可以写出递推公式为：m[ i ] = max(a[ i ] + m[ i+2 ], m[ i+1 ])。
等等，也许你要说，好像这个递推式有漏洞啊，因为前一位上的解m[ i+1 ]本身就有可能是包含或不包含a[ i+1 ]，假如m[ i+1 ]不包含a[ i+1 ]，那么岂不是还要考虑a[ i ]+m[ i+1 ]这种可能性呢？
这个递推式真的经不起推敲吗？我们不妨重新整理一下思路：由于原数组上每一元素都有取与不取两种可能，那么也就对应有包含和不包含该元素的两个子数组的最大和。对于原数组a中第i位上的元素，假设包含a[ i ]元素的子数组最大和为s[ i ]，而不包含元素a[ i ]的子数组最大和为ns[ i ]，因此所要求的不连续子数组最大和m[ i ] = max(s[ i ], ns[ i ])。那么根据题意我们可以整理出递推关系如下：
s[ i ] = max(a[ i ] + ns[ i+1 ], a[ i ] + m[ i+2 ])
ns[ i ] = m[ i+1 ]
m[ i ] = max(a[ i ] + ns[ i+1 ], a[ i ] + m[ i+2 ], m[ i+1 ])
有趣的地方在于ns[ i ] = m[ i+1 ]这一项上，根据它我们可以得到ns[ i+1 ] = m(i+2)，也就是说假如m[ i+1 ]不包含a[ i+1 ]的话，那么它一定等于m[ i+2 ]，所以a[ i ]+ns[ i+1 ]等价于a[ i ] + m[ i+2 ]，递推式m[ i ] = max(a[ i ] + m[ i+2 ], m[ i+1 ])是正确的！
从《编程之美》给出的解法中得到启发，我们也只需要使用两个变量来记录m[ i+2 ]和m[ i+1 ]的值就行了，而且同样只需要O(N)的复杂度就可以解这道题，代码如下：
int maxsum(int* a, int n)
{
int m2 = 0;
int m1 = a[ n-1 ];
for(int i = n - 2; i >= 0; i--)
{
if(m2 < 0) m2 = 0; //处理最后一位为负数或全为负数的情况
int tmp = m1;
m1 = max(a[ i ] + m2, m1);
m2 = tmp;
}
return m1;
}

我的做法：
s[0]=a[0]
s[1]=max{a[0],a[1]}
s[i]=max{s[i-1],s[i-2]+a[i]}, i>=2
int maxSum(int a[],int n){
assert(n>0);
if(n==1)
return a[0];
if(n==2)
return max(a[0],a[1]);

int* s=new int[n];
s[0]=a[0];
s[1]=max(a[0],a[1]);
for(int i=2;i<n;i++){
s[i]=max(s[i-1],s[i-2]+a[i]);
}
int ms=INT_MIN;
for(int i=0;i<n;i++){
if(s[i]>ms)
ms=s[i];
}
delete []s;
return ms;
}

4. 编程之美的内容简介

该书收集了约60道算法和程序设计题目，这些题目大部分在近年的笔试，面试中出现过，或者是被微软员工热烈讨论过。作者试图从书中各种有趣的问题出发，引导读者发现问题，分析问题，解决问题，寻找更优的解法。
本书的内容分为下面几个部分：
游戏之乐：从游戏和其他有趣问题出发，化繁为简，分析总结。
数字之魅：编程的过程实际上就是和数字及字符打交道的过程。这一部分收集了一些好玩的对数字进行处理的题目。
结构之法：汇集了常见的对字符串、链表、队列，以及树等进行操作的题目。
数学之趣：列举了一些不需要写具体程序的数学问题，锻炼读者的抽象思维能力。
书中绝大部分题目都提供了详细的解说。 每道题目后面还有一至两道扩展问题，供读者进一步钻研。
书中还讲述了面试的各种小故事，告诉读者微软需要什么样的技术人才，重视什么样的能力，如何甄别人才。回答读者关于IT业面试，招聘，职业发展的疑问。这本书的很多题目会出现在IT 行业的各种笔试，面试中。但本书更深层的意义在于引导读者思考，和读者共享思考之乐，编程之美。