[falconheart]

I'm a CS student and my current assignment is to write a program that will find the largest value in an unsorted array of integers using a recursive divide & conquer algorithm. The concept is straightforward enough, but I'm having trouble with the implementation.
From the diagram I get the idea that you use a helper function to find the larger of two numbers, to determine what to return in the next recursive call. That's simple enough to write. But I don't know how to divide & conquer an array that is unsorted. I'm also not sure what to write for a base case. Can someone help me out here?

[William_Wilson]

i would suggest using a prototype of:

public int largest(int[] array, int current_index, int size_of_array, int max){

these values if incremented properly allow you to traverse the array, and you have a base case of when current_index == size_of_array, then return the max int.

[lifeRoot]

This article might help you...
it gives some pseudo-code for quicksort:
http://en.wikipedia.org/wiki/Quicksort

[falconheart]

Thank you everyone for your input. However I am still stuck. My problem isn't that I am unable to accomplish the task of finding the largest integer in an array. It's doing it the specific way they want me to do it that is giving me fits. I could do it from one end to the other, and retain the max value that would be relatively simple. A recursive version of the bubblesort, as it were. But they want me to specifically divide & conquer, recursively, using a helper function to determine the largest of two values, an unsorted array of integers. I even have the pseudocode I just can't think of any ways to impliment it. Here I'll type the pseudocode for you.

if (anarray has only one item)
   maxArray(anarray) is the item in anarray
else if (anarray has more than one item)
   maxArray(anarray) is the maximum of
		maxArray(left half of anarray) and
		maxArray(right half of anarray)

So I understand the concept.. You divide the array in half every recursive call until you are left with essentially all the individual values, which are then compared 2 by 2 using the helper function, each returning the max to the next level above it, until the max value rises to the top. I can describe it, I can tell you the process but I can't DO it for the life of me! lol Maybe I'm just overlooking the painfully obvious (wouldnt be the first time) but can someone please help me figure out how to implement this?

[falconheart]

I - finally - did it. I'm so happy. I thought I'd go ahead and post the code here if anyone else has problems like this.

#include <iostream>
using std::cout;
using std::endl;

const int arraysize = 10;
int anArray[arraysize] = {100, 12, 89, 17, 33, 7, 97, 2, 4, 105};
int maxArray(int, int, int);
int max(int, int);

main()
{
	cout << "The largest value in anArray is: " << maxArray(arraysize, 0, (arraysize - 1)) << endl;
	system("PAUSE");
	return 0;
}

int maxArray(int arraycount, int first, int last)
{
	if (arraycount==1)
		return max(anArray[first], anArray[last]);

	else if(arraycount>1)
		return max(maxArray((arraycount /2), first, (first + last) / 2), maxArray((arraycount /2), (first + last) /2, last));

}

max(int x, int y)
{
	if (x > y)
	{
		return x;
	}
	else
	{
		return y;
	}
}

[rmitboy]

You are good at coding