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] + " ");
        }
    }

}