Uber面试题
跟定一个数组，返回最长递增子数组。如给定输入[1, 3, 2, 3, 4, 8, 7, 9]，输出应该为4，因为最长递增子数组是[2,3,4,8]
分析
最直观的就是检查所有子数组，然后返回最长的递增子数组，时间复杂度：O(n^2)。虽然这不是面试官所期望的，但是你也应该告诉他，并且声明这并不是最优解。如果我们想让算法时间复杂度低于O(n^2)，那么时间复杂度应该是O(nlogn), O(n), O(1)。O(1)看起来几乎不可能，因为我们至少需要遍历这个数组一次，所以O(n)将会是下限。如果我们考虑O(nlogn)，这通常意味着我们需要做一些排序，二叉搜索之类的事情，但因为我们并不想改变数组的顺序，排序是没有用的，二叉搜索看起来也涉及不到。
所以，O(n)就是我们的目标。
滑动窗口
如果你手动解决这个问题，你就会意识到并不是所有的子数组都需要检查。例如，假设输入是[1, 2, 3, 2, 4, 5, 6]，你从递增数组[1,2,3]开始。然而下一个数字2比上一个数字小。事实上，你可以忽略2之前所有东西，仅仅需要检查[2,4,5,6]即可。
如果你阅读了我们之前的博文Longest Substring Without Repeating Characters，滑动窗口解决办法应该非常容易，事实上，它是在线性时间里处理有关数组问题最常用的技术了。
所以我们有如下算法：
- 我们使用两个指针start和end来表示子数组arr[start:end]
- 如果当前的数组可以递增，也就意味着arr[end] > arr[end - 1]，我们可以通过使end + 1来添加一个新的数字
- 否则，我们可以忽略end之前的所有东西，直接让start = end
- 在最后，返回最长的子数组
在一开始检查一些边界条件是非常有必要的，虽然代码看起来非常简单，但是非常容易出错误。
扩展
我们将问题改成怎样返回最长的递增子序列(subsequence)？对于子序列，数字是没有必要必须保持连续的，如果输入是[1, 3, 2, 3, 4, 8, 7, 9]，那么输出应该是5，因为最长递增子序列是[2,3,4,8,9]。
我想把这个问题当成家庭作业，但我可以给你一些提示：
- 一些人可能想到brute force，然而这个问题是无法列举出所有可能性的。这种情况下，我们通常需要依赖递归算法。
- 递归算法依赖于一些递归公式
- Memorization可以有效的提升速度，但同时也会占用更多内存
- 如果你还是做不出这道题，你可以查看Subarray With Given Sum
总结
数组一类的算法题在面试中是很常见的，因为它不需要太多的知识，还能很好的考察面试者的编码能力。我并不认为这个问题有多难，但是写出来没有bug的解决方法并不容易，尤其是在有时间限制的情况下。虽然你阅读了这篇文章，但我还是认为每个人都应该写下来这个solution。