[f]izzbuzzer

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Longest contiguous increasing subarray

Sharing is caring!

Problem statement
Given an array $A$ with $N$ numbers print a longest increasing subarray in $A$.

Sample Input

1 2 3 0 5 19 23 45 -1 -2 10


Sample Output

0 5 19 23 45


Solution
We want to solve this problem in $\mathcal{O}(n)$ time complexity. The easiest approach is to to start iterating over our array and increase our sequence length as long as $A[i] \textgreater A[i-1]$. If we reach a point where $A[i] \not\textgreater A[i-1]$ we start a new sequence from index $i$. Along the way we somehow keep track of the largest sequence sequence found so far.

We can optimise our algorithm using an heuristic approach. If we reach an index $i$ where a new subsequence might start (because $A[i] \not\textgreater A[i-1]$), instead of looping forwards from index $i$ we can work our selfs backwards starting from index $i + max$ till $i$ and check if $A[i] \textgreater A[i-1]$. If $A[j] \not\textgreater A[j-1]$ for some $j \in \left[i, i + max\right]$ then we can skip and start searching for a new potential subsequence directly from index $j$. $max$ is the length of a previous contiguous increasing subarray found.

The full code is listed below.

Code

public class LongestConSubarray {
private static int[] solve(int[] a) {
int[] ans = new int[2];
int max = 1;
int i = 0;

while (i < a.length - max) {
boolean skip = false;
int j = i + max;
while (j > i) {
if (a[j] <= a[j - 1]) {
i = j;
skip = true;
break;
}
j--;
}

if (!skip) {
i = i + max;
while (i < a.length && a[i] > a[i - 1]) {
i++;
max++;
}
ans = new int[]{i - max, i - 1};
}
}

return ans;
}

public static void main(String[] args) {
int[] a = {1, 2, 3, 0, 5, 19, 23, 45, -1, -2, 10};

int[] startEnd = solve(a);

for (int i = startEnd[0]; i <= startEnd[1]; i++) {
System.out.print(a[i] + " ");
}
}

}