説明

整数 nums のリストが表示されます.その長さが少なくとも 3 であり、その値が厳密に増加してから減少する最長のサブリストの長さを返します.増加部分と減少部分の両方が空でない必要があります.

制約:

n ≤ 100,000 n は nums の長さです

例1

入力

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

出力

5

説明

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

例2

入力

nums = [1, 2, 3]

出力

0

例3

入力

nums = [3, 2, 1]

出力

0

例4

入力

nums = [1, 2, 1, 1]

出力

3

直感

配列を増やす

inc[i] : 長さを 0 から i に増やします

配列を減らす

dec[i] : 長さを i から end に減らします

実装

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;
}

時間の複雑さ

時間: O(n)

スペース: O(n)