A very simple problem, solved with the full divide-and-conquer plan, so you can see the plan by itself.
What to build
A recursive function that finds the largest number by splitting the range in half.
Requirements
- Split a range
lo .. hiatmid = (lo + hi) / 2. - Add 1 to a global counter on every call, including the first.
- Print the largest number and the number of calls.
Input
The first line has n. The second line has the n numbers.
Output
One line: the largest number, then the number of calls.
Constraints
1 ≤ n ≤ 500.
Example
Input:
5
3 9 2 7 5
Output:
9 9
Why it works
Each call that splits makes two more, and each number ends up in one single-item call. So there are always 2n − 1 calls, and T(n) = 2T(n/2) + O(1) is O(n), the same as a plain loop.
Examples
Example 1 · Input
5 3 9 2 7 5
Expected output
9 9
Example 2 · Input
1 -4
Expected output
-4 1
Hints
Hint 1
With one number in the range, that number is the answer.
Hint 2
Otherwise find the largest in each half and return the larger of the two.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int calls = 0;
int largest(int a[], int lo, int hi) {
calls++;
if (lo == hi) return a[lo];
int mid = (lo + hi) / 2;
int left = largest(a, lo, mid);
int right = largest(a, mid + 1, hi);
return left > right ? left : right;
}
int main(void) {
int n, a[500];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int answer = largest(a, 0, n - 1);
printf("%d %d\n", answer, calls);
return 0;
}