一个unsorted 1D array the longest consecutive 1s.

Example: 011011101110111111

Assumption:

array is not null

Approach:

DP. Base case m[0] = array[0];

m[] represents from 0th to ith element the length of the longest one including the ith element.

Deduction rule:

m[i] = 0 if array[i] == 0

m[i] = m[i - 1] + 1 otherwise.

public class Solution{
    public int longestOne(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int[] m = new int[array.length];
        m[0] = array[0];
        int result = m[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] == 0) {
                m[i] = 0;
            } else {
                m[i] = m[i - 1] + 1;
            }
            result = Math.max(result, m[i]);
        }
        return result;
    }
}

Time: O(n) scan the whole array.

Space: O(n) the array to store the longest length.