342 · 山谷序列

描述

给你一个长度为nn的序列，在他的子序列中让你找一个山谷序列，山谷序列定义为：

1. 序列的长度为偶数。
2. 假设子序列的长度为2n2n。则前nn个数是严格递减的，后nn个数是严格递增的，并且第一段的最后一个元素和第二段的第一个元素相同，也是这段序列中的最小值。

现在想让你找所有子序列中满足山谷序列规则的最长的长度为多少？

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

北大学霸令狐冲15年刷题经验总结的《算法小抄模板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};

    //从左到右统计递减数量

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

                }

            }

        }

    }

    //从右到左统计递减数量

    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;

    }