Array search problems are fundamental to computer science, but adding order constraints can make them challenging. A classic example is the Longest Consecutive Increasing Chain problem. The goal is to find the longest sequence of numbers in an array where each subsequent number is exactly one unit larger than its predecessor. Crucially, you must maintain the array's original ordering. This means you can only scan forward, skipping any intermediate numbers that do not fit the sequence.

For instance, given the array [0, 1, 26, 8, 9, 2, 3, 27, 1, 0, 4], the longest consecutive increasing chain is 0 → 1 → 2 → 3 → 4, which has a length of 5. The values 26, 8, 9, and 27 are simply skipped because they do not continue the incrementing pattern. Finding this sequence requires traversing the array carefully, checking all potential starting numbers.

Illustration of matching card links forming a consecutive chain
Real-World Analogy: The Card Run Metaphor

To understand this, imagine a card game where you lay out a single row of numbered cards on a table from left to right. Your objective is to build the longest run of cards that increase by exactly one (like 0 → 1 → 2 → 3 → 4).

However, you must follow a strict rule: you can only scan the cards from left to right. You cannot jump backward. You pick your starting card, say 0. Next, you scan to the right looking for a card labeled 1. When you find it, you immediately start looking from that position to the right for a 2. You ignore unrelated cards (like a 26 or a 8) because they don't fit the sequence. Once you scan the entire row, you record the run's length, then start over using the next card as your starting point to see if you can build an even longer run.

The Algorithmic Strategy

To implement this logic in Java, we can use a nested loop strategy:

  • Outer Loop: This loop designates each index in the array as a potential starting point for a sequence.
  • Inner Loop: Starting from the next index (j = i + 1), this loop scans forward looking for elements that are exactly one value higher than the current value in our sequence.
  • Tracking State: We maintain a previous variable to keep track of the last matched value and a count variable to measure the current sequence length. Every time we find a match, we increment count and update previous to the matched value.
  • Updating the Maximum: At the end of each outer loop scan, we check if our current run is the longest we've found so far and update maxCount if necessary.

Walkthrough of the Main Method Scenario

Let's trace this logic using the array [0, 1, 26, 8, 9, 2, 3, 27, 1, 0, 4]:

  1. Starting at index 0 (Value 0):
    • We scan to the right. At index 1, we find 1 (which is 0 + 1). Match! Our count becomes 1 and previous becomes 1.
    • We skip 26, 8, 9.
    • At index 5, we find 2 (which is 1 + 1). Match! Our count becomes 2 and previous becomes 2.
    • At index 6, we find 3 (which is 2 + 1). Match! Our count becomes 3 and previous becomes 3.
    • We skip 27, 1, 0.
    • At index 10, we find 4 (which is 3 + 1). Match! Our count becomes 4 and previous becomes 4.
    • The loop ends. Including the starting element, the chain length is 5 (maxCount = 5).
  2. Subsequent starting points: The outer loop shifts to index 1 (starting at value 1), then index 2 (value 26), and so on. None of these starting points can produce a chain longer than 5 elements, so the maximum remains 5.

Java Solution

Here is the complete Java implementation of this algorithm. It runs through the array using nested loops and prints the length of the longest chain found.

package io.practise.accolite;
 
public class TestSecondProblem {
    public static void main(String[] args) {
 
        int[] arr = {0, 1, 26, 8, 9, 2, 3, 27, 1, 0, 4};
 
        int count = 0;
        int maxCount = 0;
 
        for (int i = 0; i < arr.length; ++i) {
            int previous = arr[i];
 
            for (int j = i + 1; j < arr.length; ++j) {
                int diff = arr[j] - previous;
 
                if (diff == 1) {
                    ++count;
                    previous = arr[j];
                }
            }
 
            maxCount = Integer.max(maxCount, ++count);
            count = 0;
        }
 
        System.out.println(maxCount); // Outputs: 5
    }
}

Conclusion & Complexity Analysis

This nested loop approach guarantees that we check every possible starting point, making it highly robust. The time complexity is O(N^2) in the worst case because of the nested scanning structure, while the space complexity is a constant O(1) as we only need a few integer variables to track the state. This is an excellent entry-level array optimization puzzle.