342 · Valley Sequence

描述

给你一个长度为nn的序列,Lets you find a valley sequence in his subsequence,山谷序列定义为：

1. 序列的长度为偶数.
2. 假设子序列的长度为2n2n.则前nnThe number is strictly decreasing,后nnThe number is strictly increasing,并且第一段的最后一个元素和第二段的第一个元素相同,也是这段序列中的最小值.

Now I want you to find the longest length of all subsequences that satisfies the valley sequence rule？

背完这套刷题模板,真的不一样！

Ba Linghu Chong of Peking University15Summarized from the experience of brushing questions over the years《算法小抄模板Cheat Sheet》助你上岸！

微信添加【jiuzhang0607】备注【小抄】领取

• 1<=len(num)<=10001<=len(num)<=1000
• 1<=num[i]<=100001<=num[i]<=10000

样例

样例  1:
	输入: num = [5,4,3,2,1,2,3,4,5]
	输出: 8
	样例解释: 
	最长山谷序列为[5,4,3,2,2,3,4,5]

样例 2:
	输入:  num = [1,2,3,4,5]
	输出: 0
	样例解释: 
	不存在山谷序列

 

int valley(vector<int> &num) {

        // write your code here

            // write your code here

    int size = num.size();

    int left = 0;

    int right = size - 1;

    vector<int>dpleft(size, 0);

    vector<int>dpright(size, 0);

    map<int, set<int>> mapSet; //num[i],i

    int leftMax = 0;

    int rightMax = 0;

    mapSet[num[left]] = set<int>{ 0};

    //Count decreasing quantities from left to right

    for (int left = 1; left < size; left++)

    {

        auto it = mapSet.find(num[left]);

        if (it != mapSet.end())

        {

            it->second.insert(left);

        }

        else

        {

            mapSet[num[left]] = set<int>{ left };

        }

        for (int i = left - 1; i >= 0; i--)

        {

            if (num[left] < num[i])

            {

                dpleft[left] = max(dpleft[left], dpleft[i] + 1);

                if (dpleft[left] > leftMax)

                {

                    leftMax = dpleft[left];

                }

            }

        }

    }

    //Count decreasing quantities from right to left

    for (int right = size - 2; right >= 0; right--)

    {

        for (int j = right + 1; j < size; j++)

        {

            if (num[right] < num[j])

            {

                dpright[right] = max(dpright[right], dpright[j] + 1);

                if (dpright[left] > rightMax)

                {

                    rightMax = dpright[left];

                }

            }

        }

    }

    int maxRet = 0;

    for (int i = 0; i < size; i++)

    {

        if (mapSet[num[i]].size() <= 1)

        {

            continue;

        }

        set<int> tmp = mapSet[num[i]];

        for (auto it : tmp)

        {

            if (it <= i)

            {

                continue;

            }

            int minTmp = min(dpleft[i], dpright[it]) +1;

            if (minTmp > maxRet)

            {

                maxRet = minTmp;

            }

        }

    }

    return maxRet*2;

    }