http://community.topcoder.com/stat?c=problem_statement&pm=5869&rd=8078
这道题有点意思,思考理解后,就是找数组中的数A[i]满足:左边的都比它小,右边的都比它大。所以从左向右扫,不断记录更新max值,对不满足的标记false;然后从右向左扫就行了。
public class BinarySearchable { public int howMany(int[] sequence) { if (sequence.length == 0) return 0; int len = sequence.length; int max = sequence[0]; boolean valid[] = new boolean[len]; for (int i = 0; i < len; i++) valid[i] = true; for (int i = 1; i < len; i++) { if (sequence[i] > max) max = sequence[i]; else // < previous one, in-valid valid[i] = false; } int min = sequence[len-1]; for (int i = len-2; i>=0; i--) { if (sequence[i] < min) min = sequence[i]; else valid[i] = false; } int cnt = 0; for (int i = 0; i < len; i++) { if (valid[i]) cnt++; } return cnt; } }