求最长连续1的长度

题目: 由0和1组成的数组[0,1,1,0,0,1,1,1]，求最长连续1的长度

周一去笔试的题目， 我在纸上写的代码就直接连续扫描了一遍数组，记录最长连续1的数量，最后输出。

面试的时候，面试官问我，你这个时间复杂度是On，有没有不用On的解法。

今天晚上洗头发无聊乱想忽然想起来这个问题，仔细想了想，二分查找快的原理是因为数组本身是有序的，这样的数组本身就包含了一些信息，查找的时候利用了这些信息，每次查找直接去掉一半的错误答案，因此能够达到Olgn的速度。那么，在这个问题里面，包含的信息是什么？01100111 ,似乎什么也没包含，可能有位运算，01标记？什么玩意儿。。突然想到，信息在”最长”这两个字里面，最长，意味着少的就不用扫描了。

因此可以想到这样一个算法，如果我们目前发现的最长连续1的数量是6，那么我们再遇到1的时候，直接跳6位查是不是1，如果不是1，说明这段数字不可能超过6(因为末尾不是1，最多连续5个1)，如果是1的话，那么有可能是6个1，那么依次从5，4，3位倒着查，遇到不是1直接跳出，然后重复这个过程。

这样子的话，最后算出来应该是最坏情况On，不过平均情况应该要比On好。当时就在想怎么到Olgn，想错了方向.

public class MaxLength {

    public static void main(String[] args) {

        int length = 20;
        int[] data = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            data[i] = random.nextInt(2);
        }
        getMaxSuccessiveLength1(data);
        getMaxSuccessiveLength2(data);
    }

    private static int getMaxSuccessiveLength2(int[] numbers) {
        int result = 0;
        int successiveLength = 0;   //连续1的个数
        int accessTime = 0;   //从数组读取的次数
        for (int i = 0; i < numbers.length; ) {
            accessTime++;
            if (numbers[i] == 0) {
                result = (result > successiveLength) ? result : successiveLength;
                successiveLength = 0;
                i += 1;
            } else {
                successiveLength++;
                if (shouldJump(successiveLength)) {
                    result = (result > successiveLength) ? result : successiveLength;
                    int jumpDistance = result;
                    if (i + jumpDistance > numbers.length - 1) {
                        jumpDistance = numbers.length - 1 - i;
                    }
                    if (jumpDistance == 0) {
                        break;
                    }
                    i += jumpDistance;
                    for (int j = i; j > i - jumpDistance; j--) {
                        if (numbers[j] == 0) {
                            i = j + 1;
                            successiveLength = 0;
                            accessTime++;
                            break;
                        } else {
                            accessTime++;
                            if (j == i - result + 1) {
                                successiveLength += jumpDistance;   //  这一段是连续的1
                                result = (result > successiveLength) ? result : successiveLength;
                                i++;
                            }
                        }
                    }
                } else {
                    i++;
                    result = (result > successiveLength) ? result : successiveLength;
                }
            }
        }
        System.out.println("getMaxSuccessiveLength2 = " + result + ",accessTime = " + accessTime);
        return result;
    }

    /**
     * 遇到第一个1，应该向后跳
     *
     * @param successiveLength
     * @return
     */
    private static boolean shouldJump(int successiveLength) {
        return successiveLength == 1;
    }


    private static int getMaxSuccessiveLength1(int[] numbers) {
        int result = 0;
        int successLength = 0;
        int accessTime = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                result = (result > successLength) ? result : successLength;
                successLength = 0;
            } else {
                successLength++;
            }
            accessTime++;
            if (i == numbers.length - 1) {
                result = (result > successLength) ? result : successLength;
            }
        }
        System.out.println("getMaxSuccessiveLength1 = " + result + ",accessTime = " + accessTime);
        return result;
    }
  
      public static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + ",");
        }
        System.out.println();
    }
}

这个结果是和最大连续长度有关的，最大连续长度越大，跳过的位就可能越多，但速度还是On吧