# 【Prime and composite numbers】Peaks

2014-07-04

##Peaks

A non-empty zero-indexed array A consisting of N integers is given.

**A peak is an array element which is larger than its neighbors**. More precisely, it is an index P such that 0 < P < N − 1, A[P − 1] < A[P] and A[P] > A[P + 1].

For example, the following array A:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

has exactly three peaks: 3, 5, 10.

We want to **divide this array into blocks containing the same number of elements**. More precisely, we want to choose a number K that will yield the following blocks:

- A[0], A[1], ..., A[K − 1],
- A[K], A[K + 1], ..., A[2K − 1],

...- A[N − K], A[N − K + 1], ..., A[N − 1].

What's more, **every block should contain at least one peak**. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).

**The goal is to find the maximum number of blocks into which the array A can be divided.**

Array A can be divided into blocks as follows:

- one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
- two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
- three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.

However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].

The maximum number of blocks that array A can be divided into is three.

Write a function:

int solution(vector<int> &A);

that, given a non-empty zero-indexed array A consisting of N integers, returns the maximum number of blocks into which A can be divided.

**If A cannot be divided into some number of blocks, the function should return 0.**

For example, given:

A[0] = 1 A[1] = 2 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

the function should return 3, as explained above.

Assume that:

- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [0..1,000,000,000].

Complexity:

- expected worst-case time complexity is O(N*log(log(N)));
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

###思路 题目大意是希望将序列等分成c片，每片都要至少有一个peak，peak就是比左右都大的数(原序列首尾不能算)，求c的最大值 //Codility题目描述还真是啰嗦啊喂

- 用O(n)得空间统计从开始到目前为止得peak数sum[]，以及最远两peak间坐标差D
- 求最大分片数c，即求最小分片长度k，可行解k的可能范围在(D/2,min(D,n/2)]，要等分首先 n % k == 0，其次sum[k - 1], sum[2 * k - 1], sum[3 * k - 1],….sum[n - 1]这个数列有n/k项。所以外层循环k的次数等于(D/2,D]间n的约数个数（小于D/2），内层判断是否可行需要n/k的操作(小于2n/D)。于是第2步时间复杂度也是O(n)。
- 编程上要注意计算D的时候要考虑第一个和最后一个peak到首尾的距离，还有不要混淆K c的含义（大写字母做变量名很容易出错）。

###代码

```
int solution(vector<int> &A) {
int N = A.size();
vector<int> npeaks(N+1, 0);//npeaks[i]代表第i个元素（不包括）之前peak的数量
int maxD = 0;//最远两peak间坐标差D
int last_peak = -1;//处理第一个peak到起始的距离
for(int i = 1; i < N-1; i++){
if(A[i]>A[i+1] && A[i]>A[i-1]){
npeaks[i+1] = npeaks[i] + 1;
maxD = max(maxD, i - last_peak);
last_peak = i;
}
else{
npeaks[i+1] = npeaks[i];
}
}
maxD = max(maxD, N - last_peak);//处理最后一个peak到末端的距离
npeaks[N] = npeaks[N-1];
if(npeaks[N] < 1) return 0;
if(maxD > N/2) return 1;
for(int K = maxD/2; K <= maxD; K++){//slice长度
if(N%K == 0){
bool isvalid = true;
int c = N/K;//slice数量
for(int i = 1; i <= c; i++){
if(npeaks[i*K] - npeaks[(i-1)*K] < 1){
isvalid = false;
break;
}
}
if(isvalid) return c;
}
}
cout<<"fail"<<endl;
for(int K = maxD+1;;K++) {
if(N%K == 0) return N/K;//不能return K 呀
}
}
```