The Longest Plateau | Parallel Labs

The Longest Plateau | Parallel Labs
Given an array, try to develop an efficient algorithm which can compute the length of the longest plateau. A plateau is a consecutive segment of an array with equal contents. For example, if x[] = {1, 2, 3, 4, 4, 4, 5, 5, 6}, then we have six plateaus which are 1, 2, 3, 4-4-4, 5-5 and 6. And obviously the length of the longest plateaus is 3.

O(N)

	public static int execute2(int[] data) { if (data.length == 0) {
	throw new IllegalArgumentException();
	}
	int count = 1;
	int length = 1;
	for (int i = 1; i < data.length; i++) {
	if (data[i - 1] == data[i]) {
	count++;
	length = Math.max(length, count);
	} else {
	count = 1;
	}
	}
	return length;
	}

O(N^2)

	public static int execute1(int[] data) { if (data.length == 0) {
	throw new IllegalArgumentException();
	}
	int length = 1;
	for (int i = 1; i < data.length; i++) {
	if (data[i - length] == data[i]) {
	length++;
	}
	}
	return length;
	}

for each element in the array a[]

     if a[i] is equal to a[i-1]

          add 1 to the length for the current plateau

          check whether the current length is the longest one so far

     else

          reset length to 1 // plateau length is at least 1

int longestPlateau (int a[], int n)

{

    if (n == 0)

        return 0;

 

    int length = 1;

    int longestLength = 1;

 

    for (int i = 1; i<n; i++)

    {

        if (a[i] == a[i-1])

        {

            length++;

            longestLength = max(longestLength, length);

        }

        else

            length = 1;

    }

    return longestLength;

}

Read full article from The Longest Plateau | Parallel Labs