dogabi
BAN USERpublic class MaxPrefix{
public int maxPrefix(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
int min = arr[arr.length - 1];
int count = 0;
int max = 0;
int n = arr.length;
for (int i = arr.length -2; i >= 0; i--) {
if (arr[i] < min) {
max = Math.max(max, n - i -1);
min = arr[i];
}
}
return max;
}
}
import org.junit.Test;
import static org.junit.Assert.*;
public class MaxPrefixTest{
@Test
public void maxPrefixTest1() {
int[] arr = {10,-4,6,2,8,9,4};
int expected = 5;
MaxPrefix maxPrefix = new MaxPrefix();
assertEquals(expected, maxPrefix.maxPrefix(arr) );
}
@Test
public void maxPrefixTest2() {
int[] arr = {1,2,2,2,3,3,4};
int expected = 6;
MaxPrefix maxPrefix = new MaxPrefix();
assertEquals(expected, maxPrefix.maxPrefix(arr) );
}
@Test
public void maxPrefixTest3() {
int[] arr = {4,3,2,1,0};
int expected = 0;
MaxPrefix maxPrefix = new MaxPrefix();
assertEquals(expected, maxPrefix.maxPrefix(arr) );
}
@Test
public void maxPrefixTest4() {
int[] arr = {0,0};
int expected = 0;
MaxPrefix maxPrefix = new MaxPrefix();
assertEquals(expected, maxPrefix.maxPrefix(arr) );
}
}
just keep the minimum traversing from right side of the array, every time you encounter new minimum update the count. this will be O(n), I would be happy if people comment about the correctness of this algo
- dogabi June 19, 2016
- dogabi June 19, 2016