Codility - Flags

This is a solution for Codility Flags task:

Idea.

• Register all peaks.
• Maximum flag number is Math.sqrt(idxOfLastPeak - idxOfFirstPeak)+1
• Go through possible flag numbers, starting from maximum downwards. Check every time number of possible flags. 
• If number of possible flags >= number tested (taken) than return number.

 

import static java.lang.Integer.min;

class Solution {
  public int solution(int[] A) {
    int r = 0;
    final int N = A.length;
    int[] P = new int[N / 2];
    int iP = -1;
    int max_flag_number;

    for (int i = 1; i < N - 1; i++) {
      if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
        P[++iP] = i;
      } 
    }

    if (iP == -1)
      return 0;
    if (iP == 0) 
      return 1;

    max_flag_number = (int) (Math.sqrt(P[iP] - P[0])+1);
    for (int flag_taken = max_flag_number; flag_taken > 0; flag_taken--) {
      int possible_nb_flag = countFlag(P, flag_taken, iP);
      if (possible_nb_flag >= flag_taken) {
        r = min(possible_nb_flag, flag_taken);
        break;
      }
    }

    return r;
  }
  
  private int countFlag(int[] P, int space, int iP) {
    int r = 1;
    int start_flag;

    start_flag = P[0];
    for (int i = 1; i <= iP; i++) {
      if (P[i] - start_flag >= space) {
        r++;
        start_flag = P[i];
      }
    }
    return r;
  }
}