CareerCup

// O(1) for every case except
// O(logn) finding max in increase-decrease case
n = a.Length
if (n > 1) {
    front = ""
    tail  = ""

    //compare first and second element
    if (a[0] < a[1]) { front="increasing" }
    if (a[0] > a[1]) { front="decreasing" }

    //compare last and second last elements
    if (a[n-1] < a[n-2]) { tail="decreasing" }
    if (a[n-1] > a[n-2]) { tail="increasing" }

    //where they the same
    if (front == tail) { 
        print front
        //max must be one of the ends
        if (front == "increasing"){
            print "max: " + a[n-1]
        }
        else {
            print "max: " + a[0]
        }
    }
    else {
        print front +"-"+ tail
        if (front=="decreasing" && tail=="increasing" ) {
            //max must be one of the ends
            if ( a[0] > a[n-1]) {
                print "max: " + a[0]
            } 
            else {
                print "max: " + a[n-1]
            }
        }
        else {
            //max is somewhere in the middle at the inflextion point
            max = a[1]
            max = binaryMaxSearch(a, max, 1, (n-3)/2+1, n-2)
            print "max: " + max
        }
    }
}

int binaryMaxSearch([] a, start, mid, end) {
    //check for inflextion point
    if (a[mid-1] < a[mid] && a[mid] > a[mid + 1]) {
        return a[mid]
    }
    
    //not found so keep looking
    if (a[mid] < a[mid + 1]) { //go right
        return binaryMaxSearch(a, mid, (end-mid)/2+mid, end)
    }
    else { // go left
        return binaryMaxSearch(a, start, (mid-start)/2+start, mid)
    }
}

main()
{
int a[6] = {3,2,1,5,6,8};
int temp,c;
temp = a[0];
if(temp< a[1])
{
c = 1;
}
else
{
c= 2;
}
if(a[1] <a[2])
{
if(c== 1)
{
c=1;
}
else if(c == 2)
{
c = 4;
}
}
else if(a[1] >a[2])
{
if(c == 1)
{
c = 3;
}
}

switch(c)
{
case 1:
printf("increasing\n");
break;
case 2:
printf("decreasing\n");
break;
case 3:
printf("increase- decrease\n");
break;
case 4:
printf("decrease- increase\n");
break;
}
}

public static String checkArrayType(int[] array)
    {
        if(array.length <= 1)
            return "Can't evaluate";
        else
        {
            if(array[0] < array[array.length-1])
            {
                if(array[0] < array[1])
                {
                    if(array[1] < array[2])
                        return "Increasing";
                    else
                        return "Decrease-Increase";
                }
                else
                    return "Increase-Decrease";
            }
            else
            {
                if(array[0] > array[1])
                {
                    if(array[1] > array[2])
                        return "Decreasing";
                    else
                        return "Increase-Decrease";
                }
                else
                    return "Decrease-Increase";
            }
        }
    }
    
    public static int max(String arrayType, int[] array)
    {
        if(arrayType.equals("Increasing"))
            return array[array.length-1];
        else if(arrayType.equals("Decreasing"))
            return array[0];
        else if(arrayType.equals("Increase-Decrease"))
        {
            int maxNumber = -1;
            for(int i=0;i<array.length-1;i+=2)
            {
                if(i==0)
                    maxNumber = array[i];
                else if(maxNumber<array[i])
                    maxNumber = array[i];
            }
            return maxNumber;
        }
        else
        {
            int maxNumber = -1;
            for(int i=1;i<array.length;i+=2)
            {
                if(i==1)
                    maxNumber = array[i];
                else if(maxNumber<array[i])
                    maxNumber = array[i];
            }
            return maxNumber;
        }
            
    }

Your binaryMaxSearch method is designed for a sorted (monotonic) array and it has no base case. We want a variation that will check for the inflection point (still O(logn)) by checking whether the neighbors are greater or lower. Something like:

int binaryMaxSearch(int[] a, int start, int mid, int end) {
	if (a[mid-1] < a[mid] && a[mid] > a[mid + 1]) { // it's the inflection point
		return a[mid];
	else if (a[mid-1] < a[mid] && a[mid] < a[mid + 1]) { // mid is in the increasing segment of array, so go further to the right
		return binaryMaxSearch(a, mid, (end-mid)/2+mid, end);
	}
	else { // mid is in the decreasing segment of array, so go to the left
		return binaryMaxSearch(a, start, (mid-start)/2, mid;
	}
}

//Wow So many solutions already. Let me add my two cents. The java version
//I think 0(1) for finding the sorting type unless I missed something in the question
//Finding max element is 0(LOGN) only for INCR/DECR case. Everything else is O(1)
//Code in its entirety
	public enum SortType {
		INCREASING, DECREASING, INCREASEANDDECREASE, DECREASEANDINCREASE
	}
	private static SortType findArraySortType(int[] intArray) {
		if (intArray.length == 1)
			return SortType.INCREASING;// arbitary
		boolean firstIncrease = false;
		boolean secondIncrease = false;
		// check the first two elements
		if (intArray[1] > intArray[0])
			firstIncrease = true;
		else
			firstIncrease = false;
		int arrayLength = intArray.length;
		if (intArray[arrayLength - 1] > intArray[arrayLength - 2])
			secondIncrease = true;
		else
			secondIncrease = false;

		if (firstIncrease && secondIncrease)
			return SortType.INCREASING;
		if (firstIncrease && !secondIncrease)
			return SortType.INCREASEANDDECREASE;
		if (!firstIncrease && !secondIncrease)
			return SortType.DECREASING;
		if (!firstIncrease && secondIncrease)
			return SortType.DECREASEANDINCREASE;
		throw new RuntimeException("Should not happen this way.Cannot determine the sort type for this array!!");
		// check the last two elements
	}
	
	private static int getMaxElement(SortType sortType, int[] intArray) {
		if(sortType == SortType.DECREASING) return intArray[intArray.length-1];
		if(sortType == SortType.INCREASING) return intArray[0];
		//Compare the last and first for the decrease and increase and return the max one
		if(sortType == SortType.DECREASEANDINCREASE)
			return intArray[0] > intArray[intArray.length-1]?intArray[0]:intArray[intArray.length-1];

			if(sortType == SortType.INCREASEANDDECREASE) { 
			//Get the transition element and return that one.Done!!
			int lo = 0;
			int hi = intArray.length-1;
			while(true) {
				int mid = lo + (hi-lo) /2;
				if(intArray[mid] > intArray[lo]) {
					if(intArray[mid+1] < intArray[mid]) return intArray[mid];
					//still decreasing. change the lo
					lo = mid+1;
					continue;
				}
				if(intArray[mid] < intArray[lo]) {
					hi = mid+1;
				}
				
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] incArray = new int [] {1,2,3,4};
		SortType sortType = findArraySortType(incArray);
		int maxElement = getMaxElement(sortType, incArray);
		System.out.format("%s %d \n",sortType,maxElement	);
		
		int [] decArray = new int [] {-1,-2,-3,-4};
		sortType = findArraySortType(decArray);
		maxElement = getMaxElement(sortType, decArray);
		System.out.format("%s %d \n",sortType,maxElement	);

		int [] incrAndDecArray = new int [] {1,2,3,4,-1,-2,-3,-4};
		sortType = findArraySortType(incrAndDecArray);
		maxElement = getMaxElement(sortType, incrAndDecArray);
		System.out.format("%s %d \n",sortType,maxElement	);

		int [] decAndIncArray = new int [] {-1,-2,-3,-4,-1,1,2};
		sortType = findArraySortType(decAndIncArray);
		maxElement = getMaxElement(sortType, decAndIncArray);
		System.out.format("%s %d \n",sortType,maxElement	);
				
		
		
	}

To find 1)increasing 2)decreasing arrays

1) compare the first two elements

if the first element is less than the second element then the array is increasing array
max element is the last element
if the first element is greater than the second element then the array is decreasing array
max element is the first element
if the first element is equal to the second element (duplicates in the array)
then fetch the next element and repeat from step 1


To find 1)increasing -decreasing arrays 2) decreasing-increasing arrays

loop thrugth the array
compare the first element and second element
if first < second (increasing)
continue the loop till first > second(decreasing)
maxelement is the first element

else first > second (decreasing)
continue the loop till first < second(increasing)
maxelement is the second element

C++ implementation

#include <iostream>

// Special case to find max in case of Inc-Dec
int binarySearchMax (int *arr, int size) {
  int start = 0;
  int end = size - 1;
  int idx = size/2;
  for (; ;) {
    if ((arr[idx-1] < arr[idx]
	 && arr[idx] > arr [idx+1])
	|| end - start <= 1) {
      break;
    }
    if (arr[idx-1] < arr[idx]) {
      start = idx;
      idx = idx + ((end - idx)/2);
    }
    else {
      end = idx;
      idx = idx/2;
    }
  }
  return arr[idx];
}

void find (int *arr, int size) {

  if (size > 1) {
    if (arr[0] < arr[1]) {
      if (arr[size - 2] < arr[size - 1]) {
	std::cout << "Type: Increasing\n";
	std::cout << "Max: " << arr[size-1] << "\n";
      }
      else if (arr[size - 2] > arr[size - 1]) {
	std::cout << "Type: Increasing - Decreasing\n";
	std::cout << "Max: " << binarySearchMax(arr, size) << "\n";
      }
      else {
	find (arr, size - 1);
      }
    }
    else if (arr[0] > arr[1]) {
      if (arr[size - 2] > arr[size - 1]) {
	std::cout << "Type: Decreasing\n";
	std::cout << "Max: " << arr[0] << "\n";
      }
      else if (arr[size - 2] < arr[size - 1]) {
	std::cout << "Type: Decreasing - Increasing\n";
	std::cout << "Max: " << ((arr[0] > arr[size-1]) ? arr[0] : arr[size-1]) << "\n";
      }
      else {
	find (arr, size - 1);
      }
    }
    else {
      find (&arr[1], size - 1);
    }
  }
  else {
    std::cout << "Array of size 0/1 or with same elements\n";
  }
}

int main () {
  int arr1[] = {0, 1, 2, 3, 4, 5};
  int arr2[] = {5, 4, 3, 2, 1, 0};
  int arr3[] = {0, 1, 3, 5, 3, 1};
  int arr4[] = {5, 4, 0, 1, 2, 3};
  int arr5[] = {};
  int arr6[] = {1};
  int arr7[] = {0, 0};
  int arr8[] = {1, 1, 1};
  int arr9[] = {0, 1, 5, 5, 3, 1};

  find (arr1, 6);
  find (arr2, 6);
  find (arr3, 6);
  find (arr4, 6);
  find (arr5, 0);
  find (arr6, 1);
  find (arr7, 2);
  find (arr8, 3);
  find (arr9, 6);
  
  return 0;
}

public static void GetTypeAndMax(int[] arr){
        int n = arr.length;
        if (n < 2)
            return;
        String head = (arr[0] > arr[1]) ? "decreasing" : "increasing";
        String tail = (arr[n-2] > arr[n-1]) ? "decreasing" : "increasing";
        if (head.equals(tail)){
            if (head.equals("increasing"))
                System.out.printf("Increasing. Max elem : %d\r\n", arr[n - 1]);
            else
                System.out.printf("Decreasing. Max elem : %d\r\n" , arr[0]);
        }
        else{
            if (head == "increasing"){
                System.out.printf("Increasing-Decreasing. Max elem: %d\r\n" , BinSearch(arr , 0 , n-1));
            }
            else{
                System.out.printf("Decreasing-Increasing. Max elem: %d\r\n", arr[0] > arr[n - 1] ? arr[0] : arr[n - 1]);
            }
        }
    }

    public static int BinSearch(int[] arr , int l , int r){
        int m = l+ (r-l)/2;
        if (arr[m-1] < arr[m] && arr[m] > arr[m+1])
            return arr[m];

        if (arr[l] < arr[l+1] && arr[m-1] < arr[m+1]){
            return BinSearch(arr , m+1 , r);
        }
        else{
            return BinSearch(arr, l , m);
        }
    }

Here's one without Binary Search, worse case O(n)

public class ToneDetection {

	public void detect(int... data) {
		System.out.print("Data : [");
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
		System.out.print("] - ");
		
		boolean maybeInc = false, maybeDec = false;

		if (data[0] < data[1]) {
			maybeInc = true;
		} else {
			maybeDec = true;
		}

		int prev = data[1];
		if (maybeInc) {
			for (int i = 2; i < data.length; i++) {
				if (data[i] > prev) {
					prev = data[i];
				} else {
					break;
				}
			}
		} else if (maybeDec) {
			for (int i = 2; i < data.length; i++) {
				if (data[i] < prev) {
					prev = data[i];
				} else {
					break;
				}
			}
		}

		if (maybeInc) {
			if (data[data.length - 1] == prev) {
				System.out.print("Type : Increasing, ");
				System.out.println(" Min : " + data[0] + ", Max : " + data[data.length - 1]);
			} else {
				System.out.print("Type : Increasing-Decreasing, ");
				System.out.println(" Min : " + Math.min(data[0], data[data.length - 1]) + ", Max : " + prev);
			}
		}
		if (maybeDec) {
			if (data[data.length - 1] == prev) {
				System.out.print("Type : Decreasing, ");
				System.out.println(" Min : " + data[data.length - 1] + ", Max : " + data[0]);
			} else {
				System.out.print("Type : Decreasing-Increasing, ");
				System.out.println(" Min : " + prev + ", Max : " + Math.max(data[0], data[data.length - 1]));
			}
		}
	}

	public static void main(String[] args) {
		ToneDetection detection = new ToneDetection();
		detection.detect(7, 5, 3, 1, 2, 4, 6, 8);
		detection.detect(7, 5, 3, 1, 2);
		detection.detect(7, 5, 3, 1);
		detection.detect(1, 3, 5, 7, 6);
		detection.detect(3, 5, 7, 6, 4, 2);
		detection.detect(1, 3, 5, 7);
	}

}