算法导论最大子数组

1. 如何成为一名合格的算法工程师

BAT企业的算法工程师是这样工作的：问题抽象、数据采集和处理、特征工程、建模训练调优、模型评估、上线部署。（具体操作可以看阿里算法专家chris老师的算法工作流视频算法工作流是怎样的？）而一个算法工程师真正值钱的地方在于问题抽象和上线部署这两个。

2. 为什么算法导论中的数组序号是从1开始的

c语言下标从零开始是个错误，并且 index 也是一个有误导性的名词，它表示的是偏移量，明明应该用 offset。
然后 c 的徒子徒孙都学了它，导致现在很多人都误以为下标应该从 0 开始。
早期蛮荒时代，很多东西都不科学，算法导论作者致力于与落后文明作斗争，然而却遭到了楼主你的不理解，实乃编程届一大憾事。
我再说一遍，C 是结构化的汇编，下标基 0 是受到了 PDP-11 指令集的影响，更老的语言（比如 Fortran）都是基 1 的。
另外用 0/非 0 代表 false/true 也是 PDP-11 中 TST 指令和 Z 位的行为。
可能是这本书强调算法的求学思想，所以从一更加符合数学的数组规定。
但是编程的时候，指针这个东西会经常用到，如果用a(o)作为第一个元素 那么*a+n就等同于a(n) 比较方便
算法导论上的这个问题呢，我觉得我比较同意楼上的看法，这个书上面的很多的程序并不是可以敲上去直接运行的，他只是伪代码，思想而已，给人看的，人类的普遍思维是从1开始，那么书页就是从1开始了
说编程语言是给机器看而伪代码是给人看的简直是逗大家笑吧...编程语言设计出来就是给人看的....
另外从0开始在很多方便都极好....我觉得写多代码都能体会到吧..
帮算导洗地：
算法导论通篇用的是伪代码 是给人类阅读理解的 不是设计给机器去运行的
而绝大多数情况下， index 从 1 开始更符合人类直觉（如果你对这点有异议请参考的答案 ）
但少数情况下， index 从 0 开始更符合人类直觉。例如书中 hashing 还有 FFT 那块内容， index 是从 0 开始的。
其实写几天 Pascal 你就适应啦。。

3. NOIP 如果想得全国一等奖的话需要学习那些知识

必备：【模拟】高精度加、减、乘

【图论】图的表示：邻接矩阵，邻接表，边表
传递闭包和floyd
最小生成树算法(至少会一种)
单源最短路dijkstra（O(n2)）或者bellman（spfa优化，O(km)）
拓扑排序

【树】 树的先序、中序、后序遍历
树中的最长路（两遍bfs或者dfs）
并查集
【搜索】深搜、宽搜
【排序】冒泡排序、快速排序 选择排序 记数排序（又称“桶排”）
【动态规划】
01背包，无限背包
【数论】
最大公约数和最小公倍数，进制转换

需要：【模拟】
表达式求值（中缀转后缀，栈的操作）、前缀表达式、中缀表达式、后缀表达式之间的相互转化
【树】线段树 字母树
【搜索】迭代深搜
【动态规划】
树形动态规划、最长不下降子序列、最长公共子序列和最长公共子串
【排序】归并排序、堆排序

【串】 KMP（字串匹配）
【数论】 判断质数（sqrt式与筛法求素数）
【有序表】顺序表、链表、线段树及其基本操作
【图论】
Dijkstra算法的堆优化、求割点、求割边、强连通分量、欧拉路（边一次）、汉密尔顿回路（点一次）、差分约束系统
【动态规划】
状态压缩的动态规划
【分治】二分查找、二分答案、最近点对
【树】 归并树(逆序对)
【其他】
Hash、矩形切割（与线段树的比较）
【数论】欧拉函数
【几何】线段相交
【有序表】树状数组
【树】 Lca（最近公共祖先）与rmq（区间最值）

【图论】匹配算法（最大匹配，最小点覆盖，最小路径覆盖，最大独立集)
网络流算法（最大流dinic，最小费用流spfa）
【动态规划】动态规划的优化（快速幂，改变状态，优化转移，单调性，四边形不等式）
【串】 Kmp扩展、AC自动机
【数论】 中国剩余定理、概率与期望
【几何】 最远点对（旋转卡壳） 、凸包（水平序和极角序）
、半平面交
【有序表】平衡树（sbt、treap、splay）后缀数组
【其他】随机化算法、高斯消元

书：算法导论
《Free Pascal语言与基础算法》（第三版）
《全国青少年信息学奥林匹克竞赛辅导丛书（中学高级本）》
《青少年信息学奥林匹克竞赛实战辅导丛书》系列（《数学与程序设计》和《数据结构与应用》）

4. 机器学习的算法和普通《算法导论》里的算法有什么本质上的异同

作者：董可人
链接：http://www.hu.com/question/24976006/answer/29682806
来源：知乎
着作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

算法导论里的算法本质上是对有精确解的问题，如何更有效率地求得这个解。这个效率可以是计算时间更短，也可以是计算过程所需要的空间更少。

一个简单的例子是，给定一个乱序数组，如何快速的将其按从小到大的顺序重新排列，或者找到其中的中位数。这些问题都有确定且唯一的答案，一般都会有一个笨方法（穷举或遍历），只要一步一步来就可以解，所谓算法只是如何精简步骤，更快更省事地找到这个解。这些算法处理的数据也都是结构简洁且干净的类型，比如数组，二叉树，图之类的数据结构。数据规模对于这些算法而言，影响的是计算所需的时间和空间，不会因为规模改变而影响算法本身的逻辑以及计算的结果。

机器学习要解决的问题一般没有精确解，也不能用穷举或遍历这种步骤明确的方法找到解，而且需要强调的是“学习”这个属性，即希望算法本身能够根据给定的数据或计算环境的改变而动态的发现新的规律，甚至改变算法程序的逻辑和行为。

举例来说，可以是把一千份文档归类到不同的几个类别里。最简单的可以是给定几个类别，比如新闻，小说，诗歌等，算法来根据文章内容自动划分到对应的类别里。这里可以看出这个问题即使让人做，也有很多模糊不能确定的地方，比如一篇法制晚报上的犯罪纪实是应该划到新闻，还是小说呢？或者说一篇长诗比如荷马史诗是应该归在小说还是诗歌呢？机器学习算法想要解决的，就是根据从文章内容里找到的规律，来自动的给出一个划分。而不同算法可以给出不同的解，这些解都可以是“正确”的，所以一般还需要人为设计一个评判标准来决定孰优孰劣。

也可以不事先给定类别，而是让算法自己去发现文章中的规律，把相似度高的文章划分到一起。这样不同的算法可能给出不同数量的类别划分，可能是三个，四个，或者五个，也都可以是“正确”的划分。甚至什么是“相似度”，不同算法也可以给出不同解释，可以是名词动词形容词的词频及比例，也可以是句子的语法结构等。

更进一步的，你可能还希望这个算法能够用来判断一份新的文档的类别。而输入的新文档越多，也会进一步扩大初始数据集的规模，规模变大以后，原来数据中不明显的规律可能就变明显了。比如说原来一千份文档中只有一篇议论文，可能大多算法都无法把它单独划出一个类别，但当你持续输入一百份议论文后，数据中议论文的比例就变成了101/1100，差不多10%，这时候算法就应该划分出单独的议论文类别。在这个意义上，数据本身也对算法有很大的影响，这也是和算法导论中的算法的一个本质区别。

技术上说，算法导论中的算法关注点在数据结构和计算复杂度，属于离散数学的一个分支，不涉及微积分等高等数学概念。机器学习的算法本身是基于概率，统计和优化（optimization）等理论和技术，从这个角度上说给人感觉更“数学”一点。

在具体的实现细节上，机器学习的算法会大量应用算法导论中的技术来改进计算效率。但需要强调这仅仅是对底层实现来说，在算法本身的逻辑上，二者没有太多联系。换句话说，算法导论中的技术可以帮助你写出更快的程序来运行机器学习算法，但是这对机器学习要解决的问题本身是没有什么帮助的。熟练使用二叉树散列表，准确估算一个图算法的复杂度，都没有任何可能帮助你猜到在女朋友过生日时送什么礼物最好（使用了机器学习算法的淘宝君却很可能知道！）。因此不要把它们看成是搭积木拼构件的关系。

最后，如果以上解释仍然让你费解，那么还有一个更通俗的解释：算法导论是教你如何数数，而机器学习基本上相当于星座算命。一个很机械，一个靠忽悠，差不多就是这样吧。
具体分析见链接：http://www.hu.com/question/24976006