题解 | #牛妹的面试#

题目：牛妹的面试
描述：众所周知，牛妹是一个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

解法一：
思路分析：首先分析题目，在给定的序列中寻找最长的凸子序列，其中凸子序列的定义为相当于一个方程，满足的方程是 $y = x^2$ ，前半段单调递增，后半段单调递减。题目要求求出最长的凸子序列。
——在这个问题上我们可以采用动态规划的思想，首先设定一个dp的数组对象，其中dp[k][j]表示的是以第i个数结束的最大子序列，其中k记录的是当前数组是处于上升或者下降状态，初始化定义 $dp[0][0] = 1$ ， $dp[1][0] = 1$ ，其中主要分为两种情况讨论，当 $nums[i] > nums[p]$ 时， $dp[0][i] = max(dp[0][p]) + 1$ ，当 $nums[i] < nums[p]$ 时，满足 $dp[1][i] = max(dp[0][p]) + 1$ 。最终返回dp数组中的最大值即可。
实例分析：输入：[1,2,3,6,1]
——首先设定一个二维的数组，每组的大小为numberList的长度，初始化dp[0][0] = 1，dp[1][0] = 1，使用res变量记录最大值，使用两个指针变量i和j判断两个数是增还是减。
图片说明
Python核心程序为：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最大山峰序列长度
# @param numberList int整型一维数组 给定的序列
# @return int整型
#
class Solution:
    def mountainSequence(self , numberList ):
        # write code here
        len1 = len(numberList)
        if len1 == 1:
            return 1
        dp = [[0] * len1 for i in range(2)]#创建一个二维的dp数组
        dp[0][0] = 1#初始化
        dp[1][1] = 1
        res = 0#记录最大值
        for i in range(1,len1):#循环执行1到len1
            max1 = 0
            max2 = 0
            for j in range(i):
                if numberList[i] > numberList[j]:#递增判断
                    if dp[0][j] > max1:
                        max1 = dp[0][j]
                elif numberList[i] < numberList[j]:#递减判断
                    if dp[0][j] > max2:
                        max2 = dp[0][j]
                    if dp[1][j] > max2:
                        max2 = dp[1][j]
            dp[0][i] = max1 + 1
            dp[1][i] = max2 + 1
            res = max(res, dp[0][i], dp[1][i])#返回三者的最大值即为最终值
        return res

——首先分析，需要不断的判断两个值的大小，设定的两个for循环，i循环整个N的大小，j循环i前面的数，所以其时间复杂度为 $O(N^2)$ ，构建了一个二维的数组dp用来存储递增或者递减的过程，所以空间复杂度为 $O(N)$ 。
解法二：
思路分析：上述方法是通过一个二维数组来记录一个序列上升和下降的过程，dp[0]表示上升，dp[1]表示下降，所以可以解决问题，同时我们也明白了本题的核心问题就是处理上升和下降，那么我们还可以怎么解决这个问题呢，就是通过一次正循环记录递增循环的点和通过一次倒循环记录递增的点，然后通过记录的两个点相加再减1便可以得到最终的结果值。
C++核心程序：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最大山峰序列长度
     * @param numberList int整型vector 给定的序列
     * @return int整型
     */
    int dp1[10005],dp2[10005];//定义两个数组
    int mountainSequence(vector<int>& numberList) {
        // write code here
        int max1 = -1,max2 = 0;//初始化
        int len = numberList.size();
        for(int i = 0;i < len;i++){//从前往后
              dp1[i] = 1;
              for(int j = 0;j < i;j++){
                   if(numberList[j] < numberList[i])//正面递增序列
                       dp1[i] = max(dp1[i],dp1[j] + 1);
              }
         }
         for(int i = len - 1;i >= 0;i--){//从后往前
              dp2[i] = 1;
              for(int j = len - 1;j > i;j--){
                   if(numberList[i] > numberList[j])//反面递增序列
                       dp2[i]=max(dp2[i],dp2[j]+1);
              }
         }
         for(int i = 0;i < len;i++){
              max1 = max(max1,dp1[i] + dp2[i] - 1);//返回上面两个循环的和
         }
         return max1;
    }
};

——因为在这个程序中需要不断的比较数值的大小，还需要比较两次，所以其时间复杂度为 $O(N^2 + N^2 + N) = O(N^2)$ ，因为需要额外的内存空间存储递增的过程，所以其空间复杂度为 $O(N)$ 。