分治求最大值
运行下面这段程序:
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int dmax(const vector<int>& a, int l, int r) { // 求 a[l..r) 的最大值,保证 r - l >= 1
if (r - l == 1) return a[l];
int m = (l + r) / 2;
int left = dmax(a, l, m);
int right = dmax(a, m, r);
return left > right ? left : right;
}
int main() {
vector<int> a = {17, 24, 15, 13, 23};
cout << dmax(a, 0, 5) << endl;
}
(本题用 g++ -std=c++17 -O0 编译。)