Longest Strictly Increasing Run

easy Arrays

Problem

Find the longest continuous part of the array in which every number is bigger than the one before it. Print its length.

Constraints

  • 1 <= n <= 10^5

Examples

Input

5
1 3 5 4 7

Output

3

Solutions

Best approachTime O(n)Space O(1)

Walk through the array once. A bigger number extends the current run, anything else restarts it. The longest run seen is the answer.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Longest run.
 * Input   : n and the numbers.
 * Output  : The length.
 * Approach: One pass
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(int[] a) {
        // Step 1: "current" is the length of the run that ends at the current number.
        int best = 1;
        int current = 1;
        for (int i = 1; i < a.length; i++) {
            // Step 2: A bigger number extends the run. Any other number starts a new run of length 1.
            current = a[i] > a[i - 1] ? current + 1 : 1;
            best = Math.max(best, current);
        }
        return best;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve(a));
    }
}
Hints (1)
  1. What does an equal number do?