求最长递增子数组
昨天下午，有同学说他在面试时遇到一道算法题，让我 review 他的代码，可是我看了很久也没看明白，最后干脆自己做了一遍。算法的功能要求是给你一个整数数组，然后求得该数组的最长递增子数组。举个栗子，有一数组 {4,2,3,5,4,6,3,6,7,9,1,3,5}，那么我们需要得到的最长递增子数组就是 {3,6,7,9}。咋一看似乎感觉不难，于是我就笨人笨办法，于是便有了下面这个版本的算法，现在估且叫做算法一：
public static Int32[] GetSubArray(Int32[] nums)
{
if (nums == null || nums.Length == 0) {
throw new ArgumentException();
}
Int32 key = nums[0];
Int32[] findArray = new Int32[] { };
List<Int32> subArray = new List<Int32>(nums.Length) { key };
for (Int32 i = 1; i < nums.Length; i++) {
Int32 cur = nums[i];
if (cur < key) {
if (subArray.Count > findArray.Length) {
findArray = subArray.ToArray();
}
subArray.Clear();
}
subArray.Add(cur);
key = cur;
}
if (subArray.Count > findArray.Length) {
findArray = subArray.ToArray();
}
return findArray;
}
算法一的思路是：遍历原数组，相邻的两个数进行比较，如果第i项的数大于第i+1项的数，那么说明第i+1项是新的子数组的起始位置。然后再判断第 i 项之前的那个子数组subArray的长度是否最大，如果是最大则将新的最长递增数组的引用赋于已定义的临时变量findArray。然后清空子数组subArray，最后将当前数添加到子数组。如此循环直到原数组中的所有数都被遍历一次，然后退出循环，又因为这时subArray中可能还有元素，所以还需判断最后一个子数组的长度是否最大，如果是则将该子数组的引用赋于变量findArray，最后返回的findArray即为所求子数组。
分析算法一，很容易可以看出该算法的时间复杂度为O(n)，其中n为原数组的元素个数。所以原数组中元素的个数是影响算法性能的重要因素之一。还有一个影响算法一性能的因素就是算法内部的ToArray()函数，如果去掉该函数，则算法一执行百万次计算将比原先快70ms左右，所以如何优化掉ToArray()函数也是提升算法性能的一个方法。
由于原数组元素的个数无法进行优化，所以我就考虑如何去掉算法一中的两个ToArray()函数。经过对原数组进行分析后，我想到了一种只复制一次数组并且将循环内部的子操作降到最简单的方法。最终得出算法二：
public static Int32[] GetSubArray2(Int32[] nums)
{
if (nums == null || nums.Length == 0) {
throw new ArgumentException();
}
List<Int32> subArrayIndexes = new List<Int32>(nums.Length / 2) { 0 };
for (Int32 i = 0; i < nums.Length - 1; i++) {
if (nums[i] > nums[i + 1]) {
subArrayIndexes.Add(i + 1);
}
}
subArrayIndexes.Add(nums.Length);
Int32 maxArrayLength = 1, maxArrayIndex = 0;
for (Int32 i = 0; i < subArrayIndexes.Count - 1; i++) {
Int32 deltaLen = subArrayIndexes[i + 1] - subArrayIndexes[i];
if (deltaLen > maxArrayLength) {
maxArrayIndex = subArrayIndexes[i];
maxArrayLength = deltaLen;
}
}
Int32[] result = new Int32[maxArrayLength];
Array.Copy(nums, maxArrayIndex, result, 0, maxArrayLength);
return result;
}
乍一看算法二似乎不好理解，其实不难，只要找出问题的关键点，化繁为简即可。于是我就想到，如果知道了要求解的子数组的索引和长度，那不是可以以最快的速度从原数组中找到该数组吗？那么我们就把问题转化成了如何求最长递增子数组的索引和长度。
那么最长递增子数组的索引该如何求呢？分析原数组，我们可以很容易的发现一个规律，只要前一个元素大于后一个元素，那么后一个元素所在的索引就是一个递增子数组的起始索引。注意，这里说的是递增子数组，而不是最长的递增子数组。然后，根据这一规律，我们可以写出第一个循环的代码。那么，现在我们已经知道了所有递增子数组的索引了（为了便于计算，我在索引数组的头和尾分别插入了 0 和原数组长度），那么接下来我们只需要让这些索引两两进行作差，看看哪两个的差值最大，那么差值最大的那两个索引之间的元素即为最大递增子数组的元素了，于是便可以有第二个循环的代码。到此已经找到我们所需的最长递增子数组的索引和长度，然后调用Array.Copy()函数即可直接从原数组中得到结果。
最后我将两个算法进行了性能测试，结果如下：
分析算法二，有人可能会觉得用了 2 个循环怎会比只用 1 个循环跑得快呢？其实这是很多人的一个误区，至于为什么呢？我们看看算法二的第一个循环，里面的操作极其简单，而且操作的是整数，这些正是计算机所擅长的，所以循环一定会执行的极快。同样的，第二个循环里面的操作也是极其简单的，只进行减法和赋值，所以执行效率也是极高的。再对比算法一，每循环一次都要调用一次ToArray()方法，相比算法二中只做简单算术运算和逻辑运算算法一肯定会比较慢。而且在算法二中，第二个循环的次数已经远远小于第一个循环了，为啥，这是因为第一个循环已经过滤掉了子数组中元素的索引，所以当原数组元素个数比较大时，算法二的优势就相当明显了。
不过，由于这只是一道面试题，还有很多问题都没说清楚，比如这个最长递增子数组能不能包含重复元素，如果有多个最长递增子数组是否返回所有的等等这些都没有规定，再比如如果前后元素比较的次数已经超过了原数组的 1/2，那么很明显最长递增子数组的索引就是 0，就无需再去单独求索引等等，所以算法二还可以继续改进。
好吧，其实算法二的性能还可以再提高一个层次，那就是下面的算法三：
public static Int32[] GetSubArray3(Int32[] nums)
{
if (nums == null || nums.Length == 0) {
throw new ArgumentException();
}
Int32 lastArrayIndex = 0, currentArrayIndex = 0, maxArrayIndex = 0, maxArrayLength = 0;
for (Int32 i = 0; i < nums.Length - 1; i++) {
if (nums[i] > nums[i + 1]) {
lastArrayIndex = currentArrayIndex;
currentArrayIndex = i + 1;
if (currentArrayIndex - lastArrayIndex > maxArrayLength) {
maxArrayLength = currentArrayIndex - lastArrayIndex;
maxArrayIndex = lastArrayIndex;
}
}
}
if (nums.Length - currentArrayIndex > maxArrayLength) {
maxArrayLength = nums.Length - currentArrayIndex;
maxArrayIndex = currentArrayIndex;
}
Int32[] result = new Int32[maxArrayLength];
Array.Copy(nums, maxArrayIndex, result, 0, maxArrayLength);
return result;
}
我拿算法二与算法三进行性能测试，结果如下：
其实，算法三还可以继续优化，以后有时间再研究。