请教一个facebook面试题# JobHunting - 待字闺中
L*Q
1 楼
据称是facebook面试题，大意如下：
给一个int array，找出最长的递增的contiguous subarray。算法worst case是O（n）
，如何提高average 的效率。
算法我想了一个：给定array A，从左到右扫描。最初起点为A[0]找出递增的
contiguous subarray，假设结束与A[k-1]。然后以A[k]为起点扫描下一个递增的
contiguous subarray。worse case为O(n)。
关于如何提高average效率，我想到2个策略：
1. 如果剩下未扫描部分小于当前最长的递增的contiguous subarray，那剩下不用扫描
了；
2. 假设当前最长递增的contiguous subarray长度为k，接下来的扫描起点是A[i]，那
么首先比较A[i+k]和A[i+k+1]，如果A[i+k]大于A[i+k+1]，那么跳过A[i]到A[i+k]，以
A[i+k+1]作为扫描起点。因为如果A[i+k]大于A[i+k+1]，从A[i]开始的递增的
contiguous subarray长度最多为k，那可以不用扫描。
第二个策略有一个变形时当A[i+k-1] < A[i+k] < A[i+k+1]时以A[i]为扫描起点。
不知道各位还有没有其他提高average 效率的策略呢？
给一个int array，找出最长的递增的contiguous subarray。算法worst case是O（n）
，如何提高average 的效率。
算法我想了一个：给定array A，从左到右扫描。最初起点为A[0]找出递增的
contiguous subarray，假设结束与A[k-1]。然后以A[k]为起点扫描下一个递增的
contiguous subarray。worse case为O(n)。
关于如何提高average效率，我想到2个策略：
1. 如果剩下未扫描部分小于当前最长的递增的contiguous subarray，那剩下不用扫描
了；
2. 假设当前最长递增的contiguous subarray长度为k，接下来的扫描起点是A[i]，那
么首先比较A[i+k]和A[i+k+1]，如果A[i+k]大于A[i+k+1]，那么跳过A[i]到A[i+k]，以
A[i+k+1]作为扫描起点。因为如果A[i+k]大于A[i+k+1]，从A[i]开始的递增的
contiguous subarray长度最多为k，那可以不用扫描。
第二个策略有一个变形时当A[i+k-1] < A[i+k] < A[i+k+1]时以A[i]为扫描起点。
不知道各位还有没有其他提高average 效率的策略呢？
