Longest Strictly Increasing Then Decreasing Sublist

Description

You are given a list of integers nums. Return the length of the longest sublist such that its length is at least 3 and its values are strictly increasing and then decreasing. Both the increasing part and the decreasing part must be non-empty.

Constraints:

• n ≤ 100,000 where n is the length of nums

Example 1

Input

nums = [7, 1, 3, 5, 2, 0]

Output

5

Explanation

The sublist [1, 3, 5, 2, 0] is strictly increasing then decreasing.

---

Example 2

Input

nums = [1, 2, 3]

Output

0

---

Example 3

Input

nums = [3, 2, 1]

Output

0

---

Example 4

Input

nums = [1, 2, 1, 1]

Output

3

---

Intuition

• increase array
  • inc[i]: increase length from 0 to i
• decrease array
  • dec[i]: decrease length from i to end

Implementation

int solve(vector<int>& nums) {
    int n = nums.size();
    vector<int> inc(n, 1), dec(n, 1);
    // inc[i]: increase length from 0 to i
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i - 1]) {
            inc[i] = inc[i - 1] + 1;
        }
    }
    // dec[i]: decrease length from i to end
    for (int i = n - 2; i >= 0; i--) {
        if (nums[i] > nums[i + 1]) {
            dec[i] = dec[i + 1] + 1;
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (inc[i] > 1 && dec[i] > 1) {
            res = max(res, inc[i] + dec[i] - 1);
        }
    }
    return res;
}

Time Complexity

• Time: O(n)
• Space: O(n)