This is the second solution for Codility task, named Peaks.
The idea is simple:
I collect all the "peaks", and meanwhile I notice prefix sum of peak encounters.
I go through possible sizes of division as long, as I find that one, that has at least one peak in every "block" aka division.
============================================
public int solution(int[] A) {
int r = 0; // result
final int N = A.length; // size of input table
int[] P = new int[N/2]; // peaks
int pInd = -1; // last index of peaks table
int[] S = new int[N]; // sumprefix of peak count
for(int i = 1; i < N-1; i++){
if(A[i] > A[i-1] && A[i] > A[i+1]){
P[++pInd] = i; // remember peak index
S[i] = S[i-1]+1; // remember amount of peaks till this idx
} else {
S[i] = S[i-1];
}
}
if(pInd == -1) return 0; // no peaks
if(pInd == 0) return 1; // one peak means one block
S[N-1] = S[N-2]; // filling the last value of S
int minSize = max(N - P[pInd], P[0]+1); // first and last block has to have a peak
for(int size = minSize; size <=N; size++){
boolean noPeak = false;
if(N % size == 0){
int blocksAmount = N/size;
for(int blockNb = 1; blockNb < blocksAmount; blockNb++){
if( !(S[(blockNb+1)*size -1] > S[blockNb*size -1]) ){
noPeak = true;
break;
}
} // end of loop for blocks
if (!noPeak) {
r = N / size;
break;
}
}
} // end of loop for sizes
return r;
}
Brak komentarzy:
Prześlij komentarz