数组很简单，数组上的算法不简单。编程之美里大概描述了7个算法题目。虽然本人经常作为面试官面试级别还算高的技术职位，其中有些题目还是需要思考一下的。为了能更好的理解，这里把这些算法简单的汇总下。涉及到的算法如下：
| 算法 | 奇妙解法概述 |
| 数组的循环移位 | 交换 |
| 最长递增子序列 | 动态规划 |
| 和最大的子数组 | 动态规划 |
| 寻找最大的前K个元素 | 堆排序 |
| 数组分裂 | 动态规划 |
| 乘积最大的子数组 | 中间结果暂存 |
--------------------------------------------------------------------------------------
首先来看循环移位。abcd1234向左循环移动4位得到1234abcd。如果可以新开辟一个数组，则可以直接将元素copy到新位置即可。不过一般要求原地移动。我之前面试微软的时候，曾经被问到这个问题。我当时的解法是对每个元素计算目标位置，然后移动到该位置，同时将其移动它自己的目标位置。最后所有的元素都移动目标位置。这个解法很复杂，估计面试官当时也没看懂，就让我过了。当然最简单直接的解法是交换：
第一次，所有元素i和n-i交换；
第二次，题目向左移动K位，那么0到n-k内部交换；同时n-k+1到n的元素内部交换；
这个题目可以引申出另一个题目。给定一个英文句子，句子中有若干单词。要求写个算法，把句子的所有单词颠倒一下，但是单词的内部字母不变。解法类似，也是先从头到尾字母颠倒，接着各个单词再颠倒下。
其实涉及到顺序变换的题目都可以考虑交换，交换也是排序的基本操作，比如快速排序。
--------------------------------------------------------------------------------------
接着看看最长递增子序列。贪心算法是不凑效的，因为新增加的元素会影响后面的元素。遍历所有的组合是最笨的方法，复杂度是指数级别的。动态规法的方法有两种。第一种动态规划是基于这个观察：面对一个新的元素，递增子序列能否增加只和该序列的最后一个元素有关。代码表示如下：
遍历所有元素a[i]，如果lis[i]表示以a[i]结尾的最长子序列，那么lis[i+1]必然是某个lis[k]（其中k小于i+1）加上a[i+1]。所以需要遍历一下lis[k]，比较其结尾和a[i+1]，然后选出最大长度的就是lis[i+1].
第二种动态规划是查看x[v]其中v表示长度，x[v]表示具有该长度的递增子序列的 最小 结尾元素。注意最小结尾元素。lis[i]仍然表示以i结尾的最长序列长度。
初始化x[1]就是a[1]，第一个元素。x[0]是无穷小。
依次加入a[i]，如果a[i]大于某个x[v]，则lis[i]=v+1。为了保证lis[i]最大，v降序遍历。
然后是更新x[v]，如果a[i]比原来的x[v]小，则替换它。**
这两种解法复杂度都是N方。不过第二种，由于x[v]都是递增的，可以采用折半查找来提高效率。
--------------------------------------------------------------------------------
再来看看最大和的问题。最长子序列并不要求元素是连续的。最大和要求是连续的。
最简单的方法是以每个元素开始，依次往后遍历，寻找最大的和。这样就能得到start[i] 表示以i开始的最大和。再从start[i]中找出最大值，就得到最终结果。这个复杂度是n方。
我们立刻注意到很多计算是重复的。比如i=1的时候，从1到n都加了一遍；i=2的时候从2到n又加了一遍。这是一个典型的动态规划的问题，把子问题的结果保存起来。于是我们看到以a[i]开始的最大和有两种可能：a[i]，或者a[i]+start[i+1]。如果start[i+1]小于0，则选a[i]，否则选另一个。
从而得到start[i]=max(a[i],a[i]+start[i+1])。
同样的道理，如果以end[i]表示以i结尾的最大和，也可以得到end[i]=max(a[i],a[i]+end[i-1])
这个复杂度可以降到n。
-----------------------------------------------------------------------------
然后是最大k个元素的问题。
最简单的办法是遍历数组，每个元素和k个元素去比。先初始化k个极小的元素。复杂度n*k。
快速排序的交换，选定一个轴，左边的比轴小，右边的比轴大。如果右边的的个数大于k，则在右边找k个。如果小于k，在左边找，k=k-右边集合size。复杂度nlgn。
然后是堆排序。建k个元素的堆。n个元素依次加入。复杂度nlgk。值得注意的是这种方法也适合元素比较多的情况。不能读到内存里。
还有一种归并排序，分成两组，每组的前k个进行归并。
还有一种桶排序，适用于备选元素max和min差别不大的情况。可以建立一个max到min的数组，每个元素表示对应的值出现的次数。然后可以从大到小加和，找到k对应的值。
----------------------------------------------------------------------------
平均分开的问题。
说的把2n的数组分成两个长度为n的数组，要求他们sum差最小。这实际上是0-1背包问题。找出n个元素，要求小于一个数且最大。每个元素可能选中，也可能不被选中。
heap[k]表示k个元素的所有和建立的堆。堆的每个节点表示k个元素的和。第k+1个元素加入时，不止是生成heap[k+1]，还要更新heap[2..k]。因为从k+1个元素中选2个元素的和是不同于从k个元素中选择的。所以heap实际上是2维的，还有个维度是时序，heap[i+1][k+1]=heap[i+1][k]+hea[i][k]。最后从heap[n]中找到最接近总和的一般的那个集合。
这样做的问题在于会有很多集合的和是重复的。如果元素的总和不太大的话，也可以采用另一种方法。flag[k][v]这是个布尔值，表示k个元素是否能实现和为v。从flag[2n][sum]开始，依次往下减，得到flag[2n-1][1..sum].
加入新节点时，需要修改之前的数组，如下图所示：
---------------------------------------------------------------------------
最大乘积的问题，需要求出n个元素的数组中，n-1个元素的最大乘积。
这个问题比较简单，需要计算出每个元素a[i]左边的乘积，右边的乘积。然后就可以了。
-------------------------------------------------------------------------
综合讨论
仔细的观察，动态规划是解决复杂的问题的重要方法。不过经验和不断的练习也是相当重要的。