# 【Prime and composite numbers】Flags

2014-07-05

##Flags

A non-empty zero-indexed array A consisting of N integers is given. **A peak is an array element which is larger than its neighbours**. More precisely, it is an index P such that 0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1].

For example, the following array A:

A[0] = 1 A[1] = 5 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 four peaks: elements 1, 3, 5 and 10.

You are going on a trip to a range of mountains whose relative heights are represented by array A, as shown in a figure below. You have to choose how many flags you should take with you.** **The goal is to set the maximum number of flags on the peaks, according to certain rules.

**Flags can only be set on peaks.** What's more, **if you take K flags, then the distance between any two flags should be greater than or equal to K**. The distance between indices P and Q is the absolute value |P − Q|.

For example, given the mountain range represented by array A, above, with N = 12, if you take:

- two flags, you can set them on peaks 1 and 5;
- three flags, you can set them on peaks 1, 5 and 10;
- four flags, you can set only three flags, on peaks 1, 5 and 10.

You can therefore set a maximum of three flags in this case.

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A of N integers, **returns the maximum number of flags that can be set on the peaks of the array**.

For example, the following array A:

A[0] = 1 A[1] = 5 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..200,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);
- 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.

###思路

- 由于有间距要求，如果带K个flag，(K-1)*K < N ，那么K<√N
- 可以记录每个peak的下一个peak位置，于是时间复杂度为O(N +1+2+. . .+√N) =O(N + √N^2) =O(N)

###伪代码 记录每个peak的下一个peak位置

```
1 def nextPeak(A):
2 N = len(A)
3 peaks = createPeaks(A)
4 next = [0] * N
5 next[N - 1] = -1
6 for i in xrange(N - 2, -1, -1):
7 if (peaks[i]):
8 next[i] = i
9 else:
10 next[i] = next[i + 1]
11 return next
```

```
1 def flags(A):
2 N = len(A)
3 next = nextPeak(A)
4 i = 1
5 result = 0
6 while (i * i <= N):
7 pos = 0
8 num = 0
9 while (pos < N and num < i):
10 pos = next[pos]
11 if (pos == -1):
12 break
13 num += 1
14 pos += i
15 result = max(result, num)
16 i += 1
17 return result
```