Adjacent Increasing Subarrays Detection II

1. Iterate through all possible lengths k from n/2 down to 1. The first k that satisfies the condition will be the maximum, so we can return it immediately.
2. For each k, iterate through all possible starting indices a for the first subarray, from 0 to n - 2k.
3. For each pair (k, a), define two subarrays: sub1 = nums[a...a+k-1] and sub2 = nums[a+k...a+2k-1].
4. Use a helper function isIncreasing(subarray) that checks if a given subarray is strictly increasing. This function iterates through the subarray and checks if sub[i] > sub[i-1] for all i.
5. If both sub1 and sub2 are strictly increasing, we have found our maximum k and can return it.
6. If the loops complete without finding a valid k, it means no such pair of subarrays exists, so we return 0.

The most straightforward method is to test every possibility. We can iterate through all potential lengths k, starting from the largest possible (n/2) down to 1. For each k, we check every possible starting position a. At each position, we form two adjacent subarrays of length k and check if both are strictly increasing. The first value of k for which we find such a pair of subarrays is the maximum possible k.

1class Solution {2    private boolean isIncreasing(int[] nums, int start, int end) {3        for (int i = start + 1; i <= end; i++) {4            if (nums[i] <= nums[i - 1]) {5                return false;6            }7        }8        return true;9    }10 11    public int findMaximumK(int[] nums) {12        int n = nums.length;13        for (int k = n / 2; k >= 1; k--) {14            for (int a = 0; a <= n - 2 * k; a++) {15                // Check first subarray: nums[a...a+k-1]16                boolean firstOk = isIncreasing(nums, a, a + k - 1);17                // Check second subarray: nums[a+k...a+2k-1]18                boolean secondOk = isIncreasing(nums, a + k, a + 2 * k - 1);19 20                if (firstOk && secondOk) {21                    return k; // Found the largest k, return immediately22                }23            }24        }25        return 0;26    }27}

1. Create an auxiliary array, inc, of size n. inc[i] will store the length of the strictly increasing subarray ending at index i.
2. Compute the inc array in a single O(n) pass: inc[0] = 1. For i > 0, if nums[i] > nums[i-1], then inc[i] = inc[i-1] + 1, else inc[i] = 1.
3. Iterate through all possible lengths k from n/2 down to 1.
4. For each k, iterate through all starting positions a from 0 to n-2k.
5. Check if a subarray is increasing in O(1) time. A subarray nums[x...y] is strictly increasing if its length (y-x+1) is less than or equal to inc[y].
6. For a given (k, a), check if inc[a+k-1] >= k and inc[a+2k-1] >= k.
7. If both conditions are true, we've found the maximum k and can return it.

To optimize the brute-force approach, we can avoid re-calculating whether a subarray is increasing repeatedly. We can pre-process the input array to store, for each index i, the length of the strictly increasing subarray ending at i. Let's call this array inc. This pre-computation takes linear time. After this, we can proceed with the same nested loops as the brute-force approach, but the check for an increasing subarray of length k ending at index j becomes a simple O(1) lookup: inc[j] >= k.

1class Solution {2    public int findMaximumK(int[] nums) {3        int n = nums.length;4        if (n < 2) {5            return 0;6        }7 8        int[] inc = new int[n];9        inc[0] = 1;10        for (int i = 1; i < n; i++) {11            if (nums[i] > nums[i - 1]) {12                inc[i] = inc[i - 1] + 1;13            } else {14                inc[i] = 1;15            }16        }17 18        for (int k = n / 2; k >= 1; k--) {19            for (int a = 0; a <= n - 2 * k; a++) {20                boolean firstOk = (inc[a + k - 1] >= k);21                boolean secondOk = (inc[a + 2 * k - 1] >= k);22                if (firstOk && secondOk) {23                    return k;24                }25            }26        }27 28        return 0;29    }30}

1. Recognize the monotonic property: if a solution exists for length k, it also exists for any length k' < k.
2. This allows us to binary search for the answer k in the range [0, n/2].
3. Create a helper function check(k) that returns true if two adjacent increasing subarrays of length k exist.
4. Implement check(k) efficiently using precomputation. First, compute an inc array where inc[i] is the length of the increasing subarray ending at i.
5. Inside check(k), iterate from a = 0 to n - 2k. For each a, check if inc[a+k-1] >= k and inc[a+2k-1] >= k. If found, return true.
6. In the main function, perform binary search. If check(mid) is true, a solution of length mid is possible, so we store it and try for a larger k (low = mid + 1). Otherwise, mid is too large, so we search in the lower half (high = mid - 1).
7. The precomputation of the inc array is done once before the binary search.

A more efficient way to find the maximum k is to use binary search on the value of k itself. The range of possible k values is from 0 to n/2. For a given k, we can check if it's possible to find two adjacent, strictly increasing subarrays of that length. Let's call this check can_form(k). If can_form(k) is true, it implies that can_form(k-1) is also true. This monotonicity allows us to apply binary search.

The can_form(k) function can be implemented in O(n) time by first pre-calculating the lengths of increasing subarrays ending at each index, just like in the previous approach. Then, we iterate through the possible start positions a and perform an O(1) check.

1class Solution {2    public int findMaximumK(int[] nums) {3        int n = nums.length;4        int[] inc = new int[n];5        inc[0] = 1;6        for (int i = 1; i < n; i++) {7            if (nums[i] > nums[i - 1]) {8                inc[i] = inc[i - 1] + 1;9            } else {10                inc[i] = 1;11            }12        }13 14        int low = 0, high = n / 2, ans = 0;15        while (low <= high) {16            int k = low + (high - low) / 2;17            if (k == 0) {18                low = k + 1;19                continue;20            }21            if (check(k, n, inc)) {22                ans = k;23                low = k + 1;24            } else {25                high = k - 1;26            }27        }28        return ans;29    }30 31    private boolean check(int k, int n, int[] inc) {32        for (int a = 0; a <= n - 2 * k; a++) {33            boolean firstOk = (inc[a + k - 1] >= k);34            boolean secondOk = (inc[a + 2 * k - 1] >= k);35            if (firstOk && secondOk) {36                return true;37            }38        }39        return false;40    }41}

1. The core idea is to find, for each possible split point i (between index i and i+1), the maximum length k that can be formed.
2. We need two pieces of information: the length of the longest strictly increasing subarray ending at i, and the length of the longest strictly increasing subarray starting at i+1.
3. Create a DP array left[i] to store the length of the strictly increasing subarray ending at i. Compute this with a left-to-right pass: left[i] = (nums[i] > nums[i-1]) ? left[i-1] + 1 : 1.
4. Create a second DP array right[i] to store the length of the strictly increasing subarray starting at i. Compute this with a right-to-left pass: right[i] = (nums[i] < nums[i+1]) ? right[i+1] + 1 : 1.
5. After computing both arrays, iterate through all possible split points i from 0 to n-2.
6. For each i, the maximum possible length k for this split is min(left[i], right[i+1]).
7. The final answer is the maximum k found across all split points.

This optimal solution finds the answer in a single conceptual pass after some precomputation. The key insight is to consider every possible split point between two adjacent subarrays. A split point can be between index i and i+1.

For a given split point i, we need to find the longest increasing subarray ending at i and the longest increasing subarray starting at i+1. Let the lengths be len1 and len2 respectively. The largest k for which we can have two adjacent increasing subarrays of length k at this split point is min(len1, len2). By checking this for all possible split points, we can find the global maximum k.

We can precompute these lengths using two DP arrays:

• left[i]: Stores the length of the strictly increasing subarray ending at i. This is computed in a forward pass.
• right[i]: Stores the length of the strictly increasing subarray starting at i. This is computed in a backward pass.

After populating both arrays, a final pass calculates max(min(left[i], right[i+1])) for all i from 0 to n-2.

1class Solution {2    public int findMaximumK(int[] nums) {3        int n = nums.length;4        if (n < 2) {5            return 0;6        }7 8        // left[i]: length of increasing subarray ending at i9        int[] left = new int[n];10        left[0] = 1;11        for (int i = 1; i < n; i++) {12            if (nums[i] > nums[i - 1]) {13                left[i] = left[i - 1] + 1;14            } else {15                left[i] = 1;16            }17        }18 19        // right[i]: length of increasing subarray starting at i20        int[] right = new int[n];21        right[n - 1] = 1;22        for (int i = n - 2; i >= 0; i--) {23            if (nums[i] < nums[i + 1]) {24                right[i] = right[i + 1] + 1;25            } else {26                right[i] = 1;27            }28        }29 30        int maxK = 0;31        // Check every split point between i and i+132        for (int i = 0; i < n - 1; i++) {33            int k = Math.min(left[i], right[i + 1]);34            if (k > maxK) {35                maxK = k;36            }37        }38 39        return maxK;40    }41}