The maximum by divide and conquer
Write a recursive function that finds the largest element of an array by dividing it into two halves.
Example
Input
6
3 9 -1 7 9 2Output
9A big problem is divided into smaller problems of the same kind, they are solved (usually recursively), and then their solutions are combined. Binary search, merge sort, quick sort and fast exponentiation are all based on this idea.
| Step | What it does | Merge sort | Binary search |
|---|---|---|---|
| Divide | the problem into smaller parts | the array into two halves | the interval into two halves |
| Conquer | each part (recursively) | sort both halves | continue in only one |
| Combine | the solutions of the parts | merging sorted arrays, O(n) | nothing |
The complexity depends on the number of parts, their size and the cost of combining:
| Recurrence | Complexity | Example |
|---|---|---|
| T(n) = T(n/2) + O(1) | O(log n) | binary search, fast exponentiation |
| T(n) = 2T(n/2) + O(n) | O(n log n) | merge sort, the number of inversions |
| T(n) = 2T(n/2) + O(1) | O(n) | the maximum of an array, recursively |
| T(n) = T(n − 1) + O(n) | O(n²) | a badly divided problem (quick sort in the worst case) |
The gain comes from dividing the problem into equal parts: then there are only log₂ n levels of recursion.
aⁿ = (an/2)² for an even n and a · an−1 for an odd n. Every step halves the exponent – O(log n) multiplications instead of n.
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long power(long long a, long long n) {
if (n == 0) return 1; // a^0 = 1
long long p = power(a, n / 2); // solve the problem of half the size (once!)
p = p * p % MOD; // combine
if (n % 2 == 1) p = p * a % MOD; // an odd exponent
return p;
}
int main() {
long long a, n;
cin >> a >> n;
cout << power(a % MOD, n) << endl;
return 0;
}
It is important to call power(a, n / 2) once and store the result; two calls would bring the complexity back to O(n). More details in the lesson Fast exponentiation algorithm.
The best part of the array is either entirely in the left half, or entirely in the right half, or it crosses the middle. The recursion solves the first two cases, and the third one – the best suffix of the left half plus the best prefix of the right half – is computed in O(n). In total O(n log n).
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
vector<long long> a;
long long bestSum(int lo, int hi) {
if (lo == hi) return a[lo]; // one element
int mid = (lo + hi) / 2;
long long left = bestSum(lo, mid), right = bestSum(mid + 1, hi);
// the part that crosses the middle: the best suffix on the left + the best prefix on the right
long long s = 0, bestLeft = LLONG_MIN;
for (int i = mid; i >= lo; i--) { s += a[i]; bestLeft = max(bestLeft, s); }
s = 0;
long long bestRight = LLONG_MIN;
for (int i = mid + 1; i <= hi; i++) { s += a[i]; bestRight = max(bestRight, s); }
return max({left, right, bestLeft + bestRight});
}
int main() {
int n;
cin >> n;
a.resize(n);
for (auto &x : a) cin >> x;
cout << bestSum(0, n - 1) << endl;
return 0;
}
There is also an O(n) solution of this problem – Kadane's algorithm, but the divide and conquer version shows the general pattern: whatever crosses the border between the parts is computed while combining.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
Write a recursive function that finds the largest element of an array by dividing it into two halves.
6
3 9 -1 7 9 29A sorted array and a number x are given. Print how many times x appears, in O(log n).
8
1 2 2 2 3 5 5 8
233
1 2 3
401. What are the steps of the divide and conquer technique?
2. What is the complexity if T(n) = 2T(n/2) + O(n)?
3. Why is it important to call power(a, n/2) only once in fast exponentiation?