我试图解决的最新codility.com问题（只是为了提高自己的技能）。我试着配发，但没有得到超过30马克有现在这么好奇，究竟我在我的解决方案很想念。

I'm trying to solve the latest codility.com question (just for enhance my skills). I tried allot but not getting more than 30 marks there so now curious what exactly I am missing in my solution.

问题说

一个非空的零索引数组A由N个整数给出。一峰比邻国更大的数组元素。更precisely，它是一个索引p，使得

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]

例如，下面的数组答：

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

有正好四条峰：元件1，3，5和10

has exactly four peaks: elements 1, 3, 5 and 10.

您会在行程中的山脉，其相对高度重新$ P $由阵列A psented你必须选择你要多少标志与你采取的。我们的目标是在设定的峰值标志的最大数量，按一定的规则。

You are going on a trip to a range of mountains whose relative heights are represented by array A. 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.

标志只能在峰来设置。更重要的是，如果你取K标志，那么任何两个标志之间的距离应大于或等于K.指数P和Q之间的距离的绝对值|对 - Q |。

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|.

例如，鉴于数组A psented，上面有N = 12的山脉重$ P $，如果你把：

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.

写功能，给定N个整数的一个非空的零索引数组A，返回可以在阵列的峰来设置的标志的最大数量。 例如，给定上述

Write a function 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, given the array above

函数应该返回3，如以上所解释

the function should return 3, as explained above.

假设：

N是范围[1..100,000]内的整数;

N is an integer within the range [1..100,000];

数组A中的每个元素在该范围内的整数。[0..1,000,000,000]

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

复杂度：

预计最坏情况下的时间复杂度为O（N）; 预计最坏情况下的空间复杂度为O（N），超出输入存储（不包括 所需的输入参数存储）。

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).

所以，我根据我的理解问题。

So I tried this code according to my understanding of question

var A = [1,5,3,4,3,4,1,2,3,4,6,2];

function solution(A) {
 array = new Array();  
   for (i = 1; i < A.length - 1; i++) {  
    if (A[i - 1] < A[i] && A[i + 1] < A[i]) {  
     array.push(i);  
    }  
   }  

  //console.log(A);
  //console.log(array);
  var position = array[0];
  var counter = 1;
  var len = array.length;
  for (var i = 0; i < len; i++) {
    if (Math.abs(array[i+1] - position) >= len) {
        position = array[i+1];
        counter ++;
        }
    }

  console.log("total:",counter);
  return counter;

}

以上code ++工程样品数组元素： [1,5,3,4,3,4,1,2,3,4,6,2] 获取峰指数： [1，3，5，10] ，并设置标志在 1，5，和10（共3）

The above code works for sample array elements: [1,5,3,4,3,4,1,2,3,4,6,2] Get peaks at indices: [1, 3, 5, 10] and set flags at 1, 5, and 10 (total 3)

但codility.com说，它无法在阵列 [7，10，4，5，7，4，6，1，4，3，3，7] 我的code得到峰指数： [1，4，6，8] 和组标志为1和6（共2） 但coditity.com说，这应该是3旗。 （不知道为什么） 难道我错过认识这个问题？

But codility.com says it fails on array [7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7] My code get peaks at indices: [1, 4, 6, 8] and set flags at 1 and 6 (total 2) but coditity.com says it should be 3 flags. (no idea why) Am I miss-understanding the question ?

请我只想找提示/算法中。我知道这个问题已经被问的人，解决了私人聊天室，但该网页上我试图让帮助那个人，但成员而萎靡不振的我的职位是不合适的答案，所以我问这个问题在这儿了。

Please I am only looking for the hint/algo. I know this question is already asked by someone and solved on private chatroom but on that page I tried to get the help with that person but members rather flagging my posts as inappropriate answer so I am asking the question here again.

PS：您可以通过点击挑战自己尝试www.codility.com你的code

P.S: you can try your code on www.codility.com by clicking Challenge Yourself!

推荐答案

失踪100％的PHP解决方案：）

Missing 100% PHP solution :)

function solution($A)
{
    $p = array(); // peaks
    for ($i=1; $i<count($A)-1; $i++)
        if ($A[$i] > $A[$i-1] && $A[$i] > $A[$i+1])
            $p[] = $i;

    $n = count($p);
    if ($n <= 2)
        return $n;

    $maxFlags = min(intval(ceil(sqrt(count($A)))), $n); // max number of flags
    $distance = $maxFlags; // required distance between flags
    // try to set max number of flags, then 1 less, etc... (2 flags are already set)
    for ($k = $maxFlags-2; $k > 0; $k--)
    {
        $left = $p[0];
        $right = $p[$n-1];
        $need = $k; // how many more flags we need to set

        for ($i = 1; $i<=$n-2; $i++)
        {
            // found one more flag for $distance
            if ($p[$i]-$left >= $distance && $right-$p[$i] >= $distance)
            {
                if ($need == 1)
                    return $k+2;
                $need--;
                $left = $p[$i];
            }

            if ($right - $p[$i] <= $need * ($distance+1))
                break; // impossible to set $need more flags for $distance
        }

        if ($need == 0)
            return $k+2;

        $distance--;
    }
    return 2;
}