首页 > 试题广场 >

牛妹的面试

[编程题]牛妹的面试
  • 热度指数：3013 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
众所周知，牛妹是一个offer收割姬，这次面试她遇到了这样的一个问题。
给了一个序列，让找出最长的“凸子序列”
何为“凸子序列”：数列中有一个xi,使得所有x0<x1<x2….xi-1<xi且xi>xi+1>xi+1>….>xn
eg：12345431,是山峰序列，12345234不是山峰序列
注：单调递增或单调递减序列也算山峰序列；单独一个数是长度为1的山峰序列

示例1

输入

[1,2,3,6,1]

输出

5
示例2

输入

[1,2,2,1]

输出

3

说明

1,2,1

备注:
给定的序列中数都大于0 且不超过10000，且序列长度不超过1000
算法知识视频讲解
添加回答
freezerhan头像 freezerhan 
// 求两次最长上升子序列即可
int mountainSequence(vector<int>& numberList) {
  vector<int> ans;
  auto Find = [&](int l, int r, int key) ->int{
    while (l < r) {
      int mid = (l + r) >> 1;
      if (ans[mid] > key) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return r;
  };
  auto __GetLen = [&] (vector<int>& tv) ->int {
    ans.clear();
    for (int i = 0; i < (int)tv.size(); i++) {
      if (ans.empty()) {
        ans.push_back(tv[i]);
      } else {
        int tmp = ans.back();
        if (tmp < tv[i]) {
          ans.push_back(tv[i]);
        } else if (tmp > tv[i]) {
          ans[Find(0, ans.size() - 1, tv[i])] = tv[i];
        }
      }
    }
    return (int)ans.size();
  };
  auto GetLen = [&](int mid) ->int {
    int ret = 0;
    vector<int> tv;
    for (int i = 0; i < mid; i++) {
      if (numberList[i] < numberList[mid]) {
        tv.push_back(numberList[i]);
      }
    }
    ret += __GetLen(tv);
    tv.clear();
    for (int i = mid + 1; i < (int)numberList.size(); i++) {
      if (numberList[i] < numberList[mid]) {
        tv.push_back(numberList[i]);
      }
    }
    reverse(tv.begin(), tv.end());
    ret += __GetLen(tv);
    return ret + 1;
  };
  int Max = 0;
  for (int i = 0; i < (int)numberList.size(); i++) {
    Max = max(Max, GetLen(i));
  }
  return Max;
}

发表于 2020-03-27 11:01:12 回复(0)
更多回答
荒草浸风头像 荒草浸风

给定数组nums[N]

动态规划

dp[k][i]表示以第i个数为结尾的最大山峰子序列 ，k属于（0,1）表示当前数nums[i]是处于上升还是下降。shape（2，N）

初始化dp[0][0]=1,dp[1][0]=1

dp[0][i]=max(dp[0][p]) +1          p属于[0,i-1] 且nums[i]>nums[p]

dp[1][i]=max(dp[0][q],dp[0][q])+1    q属于[0,i-1] 且nums[i]<nums[p]

最后返回dp里的最大值即可 

class Solution:
    def mountainSequence(self , numberList ):
        # write code here
        N = len(numberList)
        if N==1:return 1
        dp = [[0]*N for i in range(2)]
        dp[0][0]=1
        dp[1][0]=1
        res = 0
        for i in range(1,N):
            max0 = 0
            max1 = 0
            for j in range(i):               
                if numberList[i]>numberList[j]:
                    if dp[0][j]>max0:
                        max0=dp[0][j]
                elif numberList[i]<numberList[j]:
                    if dp[0][j]>max1:
                        max1=dp[0][j]
                    if dp[1][j]>max1:
                        max1=dp[1][j]
            dp[0][i]=max0+1
            dp[1][i]=max1+1
            res = max(res,dp[0][i],dp[1][i])
        return res

发表于 2020-04-12 12:43:58 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    /**
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) {
        int Max = 0, n = numberList.size();
        int dp1[n], dp2[n];
        fill(dp1, dp1+n, 1);
        fill(dp2, dp2+n, 1);
        for(int i=1;i<n;i++)
            for(int j=0;j<i;j++)
                if(numberList[j]<numberList[i])
                    dp1[i] = max(dp1[i], dp1[j]+1);
        for(int i=n-2;i>=0;i--)
            for(int j=n-1;j>i;j--)
                if(numberList[j]<numberList[i])
                    dp2[i] = max(dp2[i], dp2[j]+1);
        for(int i=0;i<n;i++)
            Max = max(Max, dp1[i]+dp2[i]-1);
        return Max;
    }
};

发表于 2020-08-22 01:31:27 回复(0)
yeshichen头像 yeshichen 
public int mountainSequence(int[] numberList) {
        int len = numberList.length;
        int[] left = new int[len];
        int[] right = new int[len];
        for (int i = 0; i < len; i++) {
            left[i] = 1;
            for (int j = 0; j < i; j++)
                if (numberList[j] < numberList[i]) left[i] = Math.max(left[i], left[j] + 1);
        }
        for (int i = len - 1; i >= 0; i--) {
            right[i] = 1;
            for (int j = len - 1; j > i; j--)
                if (numberList[j] < numberList[i]) right[i] = Math.max(right[i], right[j] + 1);
        }
        int max = 0;
        for (int i = 0; i < len; i++) max = Math.max(max, left[i] + right[i] - 1);
        return max;
    }

发表于 2020-08-14 13:17:16 回复(0)
C/C++
萨巴鲁酱头像 萨巴鲁酱 
class Solution {
public:
    /**
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) {
        // write code here
        int res = 0;
        int n = numberList.size();
        vector<int> dp1(n, 1), dp2(n, 1);
        for(int i = 1; i < n; ++i)
            for(int j = 0; j < i; ++j)
                if(numberList[i] > numberList[j])
                    dp1[i] = max(dp1[i], dp1[j] + 1);
        for(int i = n-2; i >= 0; --i)
            for(int j = n-1; j > i; --j)
                if(numberList[i] > numberList[j])
                    dp2[i] = max(dp2[i], dp2[j] + 1);
        for(int i = 0; i < n; ++i)
            res = max(res, dp1[i] + dp2[i] - 1);
        return res;
    }
};

发表于 2020-05-19 01:51:10 回复(0)
程勇201921010625头像 程勇201921010625 
class Solution {
public:
    int mountainSequence(vector<int>& a) {
        int n = a.size();
        vector<int> dp1(n, 1), dp2(n, 1);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < i; j++)
                if(a[i] > a[j])
                    dp1[i] = max(dp1[i], dp1[j] + 1);
        for(int i = n - 1; i >= 0; i--)
            for(int j = n - 1; j > i; j--)
                if(a[i] > a[j])
                    dp2[i] = max(dp2[i], dp2[j] + 1);
        int res = 0;
        for(int i = 0; i < n; i++)
            res = max(res, dp1[i] + dp2[i] - 1);
        return res;
    }
};

发表于 2020-05-02 21:01:30 回复(0)
C/C++
henry_dai头像 henry_dai 
class Solution {
public:
    /**
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int mountainSequence(vector<int>& numberList) 
    {
        // write code here
        int** pre, ** bac;
        int max = 0;
        if (numberList.size() == 0)
            return 0;
        
        pre = new int* [numberList.size()];
        bac = new int* [numberList.size()];
        for (int i = 0; i < numberList.size(); ++i)
        {
            //元素0长度,元素1最大值
            pre[i] = new int[2];
            bac[i] = new int[2];
        }
        pre[0][0] = 1;
        pre[0][1] = numberList[0];
        bac[numberList.size() - 1][0] = 1;
        bac[numberList.size() - 1][1] = numberList[numberList.size() - 1];

        //计算当前结点 左侧递增序列长度
        for (int i = 1; i < numberList.size(); ++i)
        {
            pre[i][0] = 1;
            pre[i][1] = numberList[i];
            for (int j = 0; j < i; ++j)
            {
                if (pre[i][1] > pre[j][1] && pre[j][0] + 1 > pre[i][0])
                {
                    pre[i][0] = pre[j][0] + 1;
                }
            }
        }

        //计算当前结点 右侧递减序列长度
        for (int i = numberList.size() - 2; i >= 0; --i)
        {
            bac[i][0] = 1;
            bac[i][1] = numberList[i];
            for (int j = numberList.size() - 1; j > i; --j)
            {
                if (bac[i][1] > bac[j][1] && bac[j][0] + 1 > bac[i][0])
                {
                    bac[i][0] = bac[j][0] + 1;
                }
            }
        }

        //计算最大值
        for (int i = 0; i < numberList.size(); ++i)
        {
            if (pre[i][0] + bac[i][0] - 1 > max)
                max = pre[i][0] + bac[i][0] - 1;
        }
        return max;
    }
};

发表于 2020-04-28 23:14:45 回复(0)
铁离子头像 铁离子 
int mountainSequence(vector<int>& numberList) {
        int len = numberList.size(),res = 0;
        vector<int> dp1(len,1),dp2(len,1);
        for(int i=1;i<len;i++){
        	for(int j=0;j<i;j++){
        		if(numberList[j]<numberList[i]){
        			dp1[i] = max(dp1[j]+1,dp1[i]);
				}
				if(numberList[len-1-j]<numberList[len-1-i]){
					dp2[len-1-i] = max(dp2[len-1-i],dp2[len-1-j]+1);
				}
			}
		}
		for(int i=0;i<len;i++){
			res = max(dp1[i]+dp2[i]-1,res);
		}
		return res;
    }

发表于 2020-04-10 12:29:20 回复(0)
jerry0519头像 jerry0519 
class Solution:
    def mountainSequence(self , numberList ):
        # write code here
        l2r, r2l = [1], [1]
        for i in range(1,len(numberList)):
            temp = 1
            for j in range(len(l2r)):
                if numberList[i] > numberList[j]:
                    temp = max(temp,l2r[j]+1)
            l2r.append(temp)
        for i in range(len(numberList)-2,-1,-1):
            temp = 1
            for j in range(len(r2l)):
                if numberList[i] > numberList[-1-j]:
                    temp = max(temp,r2l[j]+1)
            r2l.append(temp)
        result = 0
        for i in range(len(l2r)):
            result = max(result, l2r[i] + r2l[-1-i] - 1)
        return result
最长上升子序列的衍生题，所谓最长凸子序列，从左边到峰顶的序列是从左到右的最长上升子序列，从峰顶到右侧的序列是从右到左的最长上升子序列。我们从左到右计算一次各个子序列的最长上升子序列，从右到左计算一次各个子序列的最长上升子序列，将对应位置的解相加，取最大。结果要减去1，因为峰顶包含了2次。
发表于 2020-03-25 22:39:45 回复(0)
zhouleilei头像 zhouleilei
谁帮忙解答一下，示例2的结果为什么是[1,2,1]

题目中要求：x0<x1<x2….xi-1<xi且xi>xi+1>xi+1>….>xn
只有小于和大于号，没有等于的情况，也没有说等于的情况合并。
编辑于 2020-03-23 18:46:59 回复(8)
提交观点

问题信息

动态规划 数组
难度：
10条回答 3596浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号