Adjacent Increasing Subarrays Detection II
Source: leetcode
Difficulty: Medium
Tags: array, binary-search

Given an array `nums` of `n` integers, your task is to find the **maximum** value of `k` for which there exist **two** adjacent subarrays of length `k` each, such that both subarrays are **strictly** **increasing**. Specifically, check if there are **two** subarrays of length `k` starting at indices `a` and `b` (`a < b`), where:


- Both subarrays `nums[a..a + k - 1]` and `nums[b..b + k - 1]` are **strictly increasing**.
- The subarrays must be **adjacent**, meaning `b = a + k`.


Return the **maximum** *possible* value of `k`.


A **subarray** is a contiguous **non\-empty** sequence of elements within an array.


 


**Example 1:**



**Input:** nums \= \[2,5,7,8,9,2,3,4,3,1]


**Output:** 3


**Explanation:**


- The subarray starting at index 2 is `[7, 8, 9]`, which is strictly increasing.
- The subarray starting at index 5 is `[2, 3, 4]`, which is also strictly increasing.
- These two subarrays are adjacent, and 3 is the **maximum** possible value of `k` for which two such adjacent strictly increasing subarrays exist.



**Example 2:**



**Input:** nums \= \[1,2,3,4,4,4,4,5,6,7]


**Output:** 2


**Explanation:**


- The subarray starting at index 0 is `[1, 2]`, which is strictly increasing.
- The subarray starting at index 2 is `[3, 4]`, which is also strictly increasing.
- These two subarrays are adjacent, and 2 is the **maximum** possible value of `k` for which two such adjacent strictly increasing subarrays exist.



 


**Constraints:**


- `2 <= nums.length <= 2 * 105`
- `-109 <= nums[i] <= 109`




C++ solution:
class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
         int flag=0;
        int prev=0;
        int curr=1;
        int ans=0;

        for(int i=1;i<nums.size();i++){
            if(nums[i-1]<nums[i]){
                curr++;
            }
            else{
                prev=curr;
                curr=1;
            }
            ans=max(ans,max(curr/2,min(prev,curr)));
        }
        return ans;
    }
};

Go solution:
var maxLengthTwoAdjacentIncreasingSubarrays int

func maxIncreasingSubarrays(input []int) int {
    var currentIncreasingCount = 1
    var previousIncreasingCount = 0
    maxLengthTwoAdjacentIncreasingSubarrays = 0

    for i := 1; i < len(input); i++ {
        updateMaxLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount, previousIncreasingCount)

        if input[i-1] >= input[i] {
            previousIncreasingCount = currentIncreasingCount
            currentIncreasingCount = 1
            continue
        }
        currentIncreasingCount++
    }
    updateMaxLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount, previousIncreasingCount)

    return maxLengthTwoAdjacentIncreasingSubarrays
}

func getLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount int, previousIncreasingCount int) int {
    return max(currentIncreasingCount/2, min(currentIncreasingCount, previousIncreasingCount))
}

func updateMaxLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount int, previousIncreasingCount int) {
    maxLengthTwoAdjacentIncreasingSubarrays = max(maxLengthTwoAdjacentIncreasingSubarrays,
            getLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount, previousIncreasingCount))
}

Java solution:
class Solution {
    public int maxIncreasingSubarrays(List<Integer> nums) {
        int prevIncrease = 0, curIncrease = 1;
        int res = 0;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums.get(i) > nums.get(i - 1)) {
                curIncrease += 1;
            } else {
                prevIncrease = curIncrease;
                curIncrease = 1;
            }
            res = Math.max(res, Math.max(curIncrease / 2, Math.min(prevIncrease, curIncrease)));
        }
        return res;
    }
}

JavaScript solution:
/**
 * @param {number[]} input
 * @return {number}
 */
var maxIncreasingSubarrays = function (input) {
    this.maxLengthTwoAdjacentIncreasingSubarrays = 0;
    let currentIncreasingCount = 1;
    let previousIncreasingCount = 0;

    for (let i = 1; i < input.length; ++i) {
        updateMaxLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount, previousIncreasingCount);

        if (input[i - 1] >= input[i]) {
            previousIncreasingCount = currentIncreasingCount;
            currentIncreasingCount = 1;
            continue;
        }
        ++currentIncreasingCount;
    }
    updateMaxLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount, previousIncreasingCount);

    return this.maxLengthTwoAdjacentIncreasingSubarrays;
};

/**
 * @param {number} currentIncreasingCount
 * @param {number} previousIncreasingCount 
 * @return {number}
 */
function getLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount, previousIncreasingCount) {
    return Math.max(Math.floor(currentIncreasingCount / 2), Math.min(currentIncreasingCount, previousIncreasingCount));
}

/**
 * @param {number} currentIncreasingCount
 * @param {number} previousIncreasingCount 
 * @return {void}
 */
function updateMaxLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount, previousIncreasingCount) {
    this.maxLengthTwoAdjacentIncreasingSubarrays = Math.max(this.maxLengthTwoAdjacentIncreasingSubarrays,
            getLengthTwoAdjacentIncreasingSubarrays(currentIncreasingCount, previousIncreasingCount));
}

Python solution:
class Solution:
    def maxIncreasingSubarrays(self, nums):
        prev = 0
        curr = 1
        ans = 0

        for i in range(1, len(nums)):
            if nums[i - 1] < nums[i]:
                curr += 1
            else:
                prev = curr
                curr = 1
            ans = max(ans, max(curr // 2, min(prev, curr)))
        
        return ans

Ruby solution:
def max_increasing_subarrays(nums)
  n = nums.size
  run = Array.new(n, 1)
  (n - 2).downto(0) { |i| run[i] = nums[i] < nums[i+1] ? run[i+1] + 1 : 1 }
  lo = 1
  hi = n / 2
  ans = 0
  while lo <= hi
    mid = (lo + hi) / 2
    found = false
    limit = n - 2 * mid
    (0..limit).each do |a|
      if run[a] >= mid && run[a + mid] >= mid
        found = true
        break
      end
    end
    if found
      ans = mid
      lo = mid + 1
    else
      hi = mid - 1
    end
  end
  ans
end