CareerCup

/*
step1 : Maintain two counters count1 & count2

count1 contains size of LessThan zigzag order (which starts with <). e,g  a<b>c<d
count2 contains size of GreaterThanzigzag order (which starts with >). e,g  x>y<z>i<j
step2: increase count1 by 1 when you add a new element to LessThan ZigZag order.
increase count2 by 1 when you add a new element to GreaterThan ZigZag order.
Step3: if ith element doesnot meet condition, then  skip it.
*/
int maxZigZagLength(vector<int> &vec)
{
	bool lessThan = true;
	bool greaterThan = true;
	int count1 = 0, count2 = 0;

	for (int i = 1; i < vec.size(); i++)
	{
		if ((lessThan && vec[i - 1] < vec[i]) || (!lessThan && vec[i - 1] > vec[i]))
		{
			lessThan = !lessThan; 
			count1++;
		}

		if ((greaterThan && vec[i - 1] > vec[i]) || (!greaterThan && vec[i - 1] < vec[i]))
		{
			greaterThan = !greaterThan;
			count2++;
		}
	}
	count1++, count2++;
	cout << "Less Than count1 = " << count1 << " , count2 = " << count2 << endl;
	return count1 > count2 ? count1 : count2;
}

int main()
{
	vector<int> vec = { 1,42,59,43,68,44 }; // answer is 1 < 42 > 43< 68 > 44
	cout << "lenght = " << maxZigZagLength(vec) << endl; 

	vector<int> vec1 = { 100,42,54,2,5 }; // answer is  100> 42 <54>2 < 5
	cout << "lenght = " << maxZigZagLength(vec1) << endl;

	vector<int> vec2 = { 1,42,54,20,1 }; // answer is 1<42>20 or 42 < 54 > 20
	cout << "lenght = " << maxZigZagLength(vec2) << endl;
	getchar();
}

Please let me know if you find any bugs in approach

Take the input as Integer Array.
Store the position where the first greater than or less than occurs (keep skipping if the elements are equal). Store the comparison value i.e. 1 or -1 in first
From that point on, find the next less than, greater than (next in this case) and compare it the last stored i.e first in this case.
At then end, the number of less thans and greater thans are found. Return result+!

public class ZigZagArrayMaxDemo {

    public static int maxZigZagLength(Integer[] input) {
        if(input.length ==0 ) throw new IllegalArgumentException("array length is 0");
        int result = 0;

        int first = 0;
        int startIndex = 0;
        for(int i = 0; i < input.length - 1; i++) {
            first = input[i].compareTo(input[i+1]);
            if(first !=0) {
                startIndex = i+1;
                result = 1;
                break;
            }
        }

        if(first == 0) return 0;
        int next;
        for (int i = startIndex; i < input.length - 1; i++) {
            next = input[i].compareTo(input[i+1]);
            if(next == 0) continue;

            if((next != first)) {
                result++;
                first = next;
            }

        }


        return result+1;
    }

    public static void main(String[] args) {
        Integer[] inputArray = {1,42,54,20,1 };
        System.out.println(maxZigZagLength(inputArray));
    }
}