LeetCode Daily Problem P3350 Detect Adjacent Increasing Subarrays II

---

Timeline

Timeline

2025-10-15

init

Array, optimized from O(n^3) to O(n^2) and then to O(n)

---

Problem:

P3350 Check Adjacent Increasing Subarrays II

https://leetcode.cn/problems/adjacent-increasing-subarrays-detection-ii/description/?envType=daily-question&envId=2025-10-15

$$ O(n^3)$$ Brute force

Direct brute force, nothing much to say, it timed out.

#include <vector>
using std::vector;

class Solution {
public:
  int maxIncreasingSubarrays(vector<int> &nums) {
    int n = nums.size();
    // n starts from 2
    int k = n / 2;
    int a, b, i;
    int flag = true;

    while (k > 0) {
      a = 0;     // 0..k-1
      b = a + k; // a+k.. b+k-1
      while (b + k - 1 < n) {
        flag = true;
        for (i = 1; i < k; i++) {
          if (nums[a + i] > nums[a + i - 1] && nums[b + i] > nums[b + i - 1]) {
            continue;
          } else {
            a++;
            b = a + k;
            flag = false;
            break;
          }
        }
        if (flag) {
          return k;
        }
      }
      k--;
    }
    return 0;
  }
};

#include <stdio.h>
int main() {
  vector<int> vec = {19, -14, 0, 9};
  Solution s;
  printf("%d\n", s.maxIncreasingSubarrays(vec));
}

$$O(n^2)$$ Preprocessing optimization

We define an array inc, where inc[i] represents the length of the longest increasing subarray ending at nums[i]. For two adjacent increasing segments starting at a and b, they must satisfy inc[a + k - 1] >= k && inc[b + k - 1] >= k. This also timed out, wuwu.

#include <vector>
using std::vector;

class Solution {
public:
  int maxIncreasingSubarrays(vector<int> &nums) {
    int n = nums.size();
    int i;
    // n starts from 2
    int k = n / 2;
    int a, b;
    vector<int> inc(n, 1);
    for (i = 1; i < n; i++) {
      if (nums[i] > nums[i - 1]) {
        inc[i] = inc[i - 1] + 1;
      }
    }

    while (k > 0) {
      a = 0;
      b = a + k;
      while (b + k - 1 < n) {
        if (inc[a + k - 1] >= k && inc[b + k - 1] >= k) {
          return k;
        } else {
          a++;
          b = a + k;
        }
      }
      k--;
      if (k == 1) {
        return 1;
      }
    }
    return 1;
  }
};

$$O(n)$$

If we know all pairs of adjacent strictly increasing segments, then k is the minimum of the two segments. We traverse the array once and find the maximum k. But note that we also need to record the length of a single strictly increasing segment, because it can also be split into two adjacent strictly increasing segments.

// #include <limits.h>
#include <vector>
using std::vector;

class Solution {
public:
  // Traverse the array and compute the lengths of all consecutive increasing segments.
  int maxIncreasingSubarrays(vector<int> &nums) {
    int n = nums.size();
    int i;

    int curr_len = 1;
    // Set prev_len to 0; otherwise, max would be updated on the first check even when there is no previous segment.
    int prev_len = 0;
    int max_val = 0;

    int len_max = 0;
    if (n <= 1) {
      return 0;
    }

    for (i = 1; i < n; i++) {
      if (nums[i] > nums[i - 1]) {
        curr_len++;
      } else {
        max_val = std::max(max_val, std::min(curr_len, prev_len));
        len_max = std::max(curr_len, len_max);
        prev_len = curr_len;
        curr_len = 1;
      }
    }
    // Finally, don't forget to update len_max.
    len_max = std::max(len_max, curr_len);

    max_val = std::max(max_val, std::min(curr_len, prev_len));
    max_val = std::max(len_max / 2, max_val);

    return max_val;
  }
};