厳密に増加してから減少するサブリスト

6708 ワード
algorithms programming cpp テキストリンク

説明



整数 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)
    • .netにおける統一認証管理
    DOM ツリーのトラバース