Problem of The Day: Adjacent Increasing Subarrays Detection II

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        l, r = 0, len(nums) // 2
        ans = 0

        def is_valid(k):
            N = len(nums)
            for i in range(0, N - k + 1):
                arr1 = nums[i:i + k]
                arr2 = nums[i+k:i+k+k]
                if len(arr1) != k or len(arr2) != k:
                    continue
                is_valid = True
                for a in range(1, k):
                    if arr1[a - 1] >= arr1[a]:
                        is_valid = False
                        break
                if not is_valid:
                    continue

                for b in range(1, k):
                    if arr2[b - 1] >= arr2[b]:
                        is_valid = False
                        break
                if not is_valid:
                    continue

                if is_valid:
                    return True

            return False

        while l <= r:
            m = l + (r - l) // 2
            if is_valid(m):
                ans = m
                l = m + 1
            else:
                r = m - 1
        return ans

Improved Algorithm [Accepted]

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        inc = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                inc[i] = inc[i - 1] + 1

        # Check if we can find two consecutive increasing subarrays of size k
        def is_valid(k):
            for i in range(k, n):
                if inc[i] >= k and inc[i - k] >= k:
                    return True
            return False

        # Binary search for maximum k
        l, r, ans = 0, n // 2, 0
        while l <= r:
            m = (l + r) // 2
            if is_valid(m):
                ans = m
                l = m + 1
            else:
                r = m - 1
        return ans

Editorial

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        cnt, precnt, ans = 1, 0, 0
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                cnt += 1
            else:
                precnt, cnt = cnt, 1
            ans = max(ans, min(precnt, cnt))
            ans = max(ans, cnt // 2)
        return ans