Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] < A[P] > A[P + 1].
Solution
#include <algorithm>#include <iterator>int solution(vector<int> &A) { // write your code in C++11 (g++ 4.8.2) int s = int(A.size()); if (s < 3) return 0; int i = 1; vector<int> factors; while (i * i < s) { if (s % i == 0) { factors.push_back(i); factors.push_back(s / i); } i++; } if (i * i == s) { factors.push_back(i); } sort(factors.begin(), factors.end()); vector<int> peaks(s, 0); int peak_num = 0; for (int j = 1; j < s - 1; j++) { if ((A[j] > A[j - 1]) && (A[j] > A[j + 1])) { peaks[j] = 1; peak_num++; } } if (peak_num == 0) return 0; if (peak_num == 1) return 1; vector<int> pre_sum_peaks; int ss = 0; for (auto j: peaks) { ss += j; pre_sum_peaks.push_back(ss); } for (int j = 1; j < int(factors.size()); j++) { bool no_peak = false; for (int k = 0; k < s; k += factors[j]) { int start_s = (k == 0) ? 0 : pre_sum_peaks[k - 1]; if (pre_sum_peaks[k + factors[j] - 1] - start_s == 0) { no_peak = true; break; } } if (!no_peak) return s / factors[j]; } return 0; }