Roman C - 2 years ago 609
Java Question

# Find an ascending slice of the array with maximum size

I have a coding test that I have tried to solve.

There's an array with integers like this

``````int[] A = {2,2,2,2,1,2,-1,2,1,3};
``````

A slice of the array is a pair of integers (P,Q) such that 0 ≤ P ≤ Q < N. Integer P is called the beginning of the slice, integer Q is called ending of the slice. The number Q - P + 1 is called the size of the slice. A slice (P,Q) is called ascending if the corresponding items of the array are in strictly increasing sequence A[P] < A[P+1] <...<A[Q-1] < A[Q].

The slice like (P,P) with only one item is considered to be ascending.

Pair (0,3) is a slice of array A of size 4 that is not ascending. Pair (2,2) is a slice of size 1 that is ascending. Pair (4,5) is a slice of size 2 that is not ascending. Pairs (6,7) and (8,9) are other slices of size 2 that are ascending. There's no more slices in array A that has a size greater than 2 that are ascending.

We need a function that returns the beginning of any ascending slice of array A which has a maximum size. For example the given array should return 4, or 6, or 8.

The following array has three items

``````int[] A = {30,20,10};
``````

the function may return 0, 1, or 2 because all ascending slices of this array have a size 1;

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

• Each element of array A is an integer within the range
`[Integer.MIN_VALUE, Integer.MAX_VALUE]`
;

• Array A is not sorted.

Complexity:

• Expected worst-case time complexity is O(N);

• Expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input array can be modified.

Attempted solution:

``````  public int solution(int[] A) {
int P =0,P1 = 0, Q = 1, max = 0;
int n = A.length;
for (int i = 0; i < n - 2; i++) {
if (A[i] != A[i+1] && A[i] != A[i+2] && A[i+1] != A[i+2]) {
P =P1;
Q = i + 1;
int size = Q - P1 + 1;
if (size > max && isAscending(A, P, Q))
max = size;
P1 = Q;
}
}
return P;
}

boolean isAscending(int[] A, int P, int Q) {
int n = A.length;
for (int i = P; i <= Q; i++) {
if (A[i] >= A[i+1]) return false;
}
return true;
}
``````

For the first array it returns 7 and fails the test, for the second array it passes with 0.

Any help would be greatly appreciated.

You can start with best solution `index = 0` and `length = 1`.

Set a current ascending slice starting in 0 (`current = 0`).

Then, loop the array and for each number you can check if it belongs to the current ascending slice or not (`A[i - 1] < A[i]`).

If not belongs to the current ascending slice, then set your current ascending slice starting in the current index (`current = i`)

Compare your best solution with the current slice (`i - current + 1 > length`) and update it if is better.

``````public int solution(int[] A)
{
int maxSliceStart = 0;
int maxSliceLength = 1;

int currentSliceStart = 0;

for (int i = 1; i < A.Length; i++)
{
if (A[i - 1] >= A[i]) currentSliceStart = i;

if (i - currentSliceStart + 1 /* length of the current slice */ > maxSliceLength)
{
maxSliceStart = currentSliceStart;
maxSliceLength = i - currentSliceStart + 1;
}
}

return maxSliceStart;
}
``````

EDIT:

If you want ALL slices with the maximum length:

``````public List<int> solution(int[] A)
{
List<int> maxSliceStarts = new List<int> { 0 };
int maxSliceLength = 1;

int currentSliceStart = 0;

for (int i = 1; i < A.Length; i++)
{
if (A[i - 1] >= A[i]) currentSliceStart = i;

int currentSliceLength = i - currentSliceStart + 1;

if (currentSliceLength > maxSliceLength)
{
maxSliceStarts.Clear();
maxSliceLength = currentSliceLength;
}

if (currentSliceLength == maxSliceLength)