题解 | #牛妹的面试#

描述：
众所周知，牛妹是一个offer收割姬，这次面试她遇到了这样的一个问题。给了一个序列，让找出最长的“凸子序列”
何为“凸子序列”：数列中有一个xi,使得所有x0<x1<x2….xi-1<xi且xi>xi+1>xi+1>….>xn
eg：12345431,是山峰序列，12345234不是山峰序列
注：单调递增或单调递减序列也算山峰序列；单独一个数是长度为1的山峰序列
题目中有几个关键点：
1.要求的子序列可以不连续，如果是求子串则需要连续
2.求最长凸子序列长度就是求正向遍历序列的最长递增子序列长度+反向遍历的序列的最长递增子序列长度-1
方法一：动态规划
动态规划的特点就是当前解可以由上一个阶段的解推出，因此我们可以把要求解的问题简化成一个更小的子问题，子问题具有相同的求解方法，求最长递增子序列就符合这个特性，我们先求正向数组的最长递增子序列，逆向数组的求法同理

先找状态，这里的dp[i]就是表示以numberList[i]结尾的最长子序列的长度,这个值就是状态
如何推出状态转移方程呢？这里用到数学归纳法，要求前n个数的最长递增子序列，我们先求前n-1个数的最长递增子序列,求前n-1个数的最长递增子序列需要求前n-2个数的最长递增子序列...直到求第1个数的最长递增子序列，即1，

$eg:$
比如数组 $(1,2,3,6,1)$
前一个数 $dp[0]=1$ ,子序列为{1},
前两个数,2前面有1小于2， $dp[1]=dp[0]+1=2$ ,子序列 $(1,2)$
前三个数,3前面有1,2小于3, $dp[2]=dp[1]+1=3$ ,子序列为 $(1,2,3)$
前四个数，6前面有1,2,3小于6， $dp[3]=dp[2]+1=4$ ，子序列为 $(1,2,3,6)$
前五个数,1前面没有数小于1，初始化值不变， $dp[4]=1$
$LIS= max(dp[0],dp[1]...dp[i])$
同理求逆置后的数组的最长递增子序列 $res=max(dp1[0]+dp2[0]-1,dp1[1]+dp2[1]-1...dp1[i]+dp2[i]-1)$

图片说明
具体代码如下：

import java.util.*;


public class Solution {
    /**
 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
      *
 返回最大山峰序列长度
 @param numberList int整型一维数组 给定的序列
 @return int整型
      */
     public int mountainSequence (int[] numberList) {
         // write code here
         int i,j,n=numberList.length;
         int[]dp1=new int[n];
         int[]dp2=new int[n];
         //dp[i]表示以numberList[i]结尾的最长子序列长度，最小为1，所以dp数组全部初始化为1
         Arrays.fill(dp1,1);
         Arrays.fill(dp2,1);
         //正向遍历数组填充dp1数组
         for(i=0;i<n;i++){
             for(j=0;j<i;j++){
                 if(numberList[i]>numberList[j])
                     //找到前面结尾比numberList[i]小的子序列，将numberList[i]接到后面，子序列长度+1
                     dp1[i]=Math.max(dp1[i],dp1[j]+1);
                 if(numberList[n-i-1]>numberList[n-j-1])
                     dp2[n-i-1]=Math.max(dp2[n-i-1],dp2[n-j-1]+1);
             }
         }
         //最长子序列长度=正向遍历的最长子序列长度+反向遍历的最长子序列长度-1
         int res=0;
         for(i=0;i<n;i++)             //顶点被算了两次，需要减1
            res=Math.max(res,dp1[i]+dp2[i]-1);
         return res;
     }
 }

复杂度：

时间复杂度：双重循环，平均时间复杂度为 $图片说明$
空间复杂度：与两个dp数组的大小有关， $O(n)$
（n为数组的大小）

方法二：贪心+二分
动态规划算法的时间复杂度达到 $图片说明$ ，在时间限制比较苛刻的情况下可能会超时，我们可以采用贪心+二分的算法，时间复杂度为 $图片说明$

新建 $dp1$ 数组， $dp1[i]$ 表示以 $numberList[i]$ 结尾的最长子序列的长度
新建一个 $dp$ 数组， $dp[i]$ 表示长度为 $i$ 的 $LIS$ 结尾元素的最小值， $dp$ 数组是一个上升子序列，只有它的结尾元素越小，才越有利于在后面接其他元素，也就越可能更长，因此我们需要维护 $dp$ 数组
对于每一个 $numberList[i]$ ,如果 $numberList[i]>dp[当前LIS长度]$ ，就把 $numberList[i]$ 接到dp数组的后面，当前 $LIS$ 长度加一, $dp1[i]=size$ ,即记录以 $numberList[i]$ 结尾的最长子序列的长度，否则如果 $numberList[i]<dp[当前LIS长度]$ ,就用 $numberList[i]$ 去更新 $dp[i]$ ,由于 $dp$ 数组的元素递增，我们可以采用二分法来查找第一个大于等于 $numberList[i]$ 的数，做一次替换即可，并且更新 $dp1[i]$ 的值
接着我们从右往左扫描一遍数组，记录 $dp2$ 数组
$res=max(dp1[0]+dp2[0]-1,dp1[1]+dp2[1]-1...dp1[i]+dp2[i]-1)$

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最大山峰序列长度
     * @param numberList int整型一维数组 给定的序列
     * @return int整型
     */
    //贪心+二分
    public int mountainSequence (int[] numberList) {
        // write code here
        int n = numberList.length;
        if(numberList == null  || n== 0)
            return 0;
        if(n == 1)
            return 1;
        int[] dp1 = new int[n], dp2 = new int[n], dp = new int[n];
        //dp1[i],dp2[i]表示以numberList[i]结尾的最长子序列长度，最小为1，所以dp数组全部初始化为1
        Arrays.fill(dp1,1);
        Arrays.fill(dp2,1);
        //dp[i]表示长度为i的LIS结尾元素的最小值
        dp[0] = numberList[0];
        //size统计当前dp数组的大小
        int size = 1;
        for(int i = 1; i < n; i++){
            //对于每一个numberList[i]如果大于dp[当前最长的LIS长度-1]则将numberList[i]接到dp[size-1]后面，同时size++
            if(numberList[i] > dp[size-1]){
                dp[size++] = numberList[i];
                //记录以numberList[i]结尾的最长子序列长度
                dp1[i] = size;
            }else{
                //二分法查找dp数组中第一个大于等于numberList[i]的数dp[pos]，用numberList[i]更新dp[pos]
                int pos = bs(dp, 0, size-1, numberList[i]);
                dp[pos] = numberList[i];
                dp1[i] = pos+1;
            }
        }
        size = 1;
        dp[size-1] = numberList[n-1];
        for(int i = n-2; i >= 0; i--){
           if(numberList[i] > dp[size-1]){
               dp[size++] = numberList[i];
               dp2[i] = size;
           }else{
                int pos = bs(dp, 0, size-1,numberList[i]);
                dp[pos] = numberList[i];
                dp2[i] = pos+1;
           }
        }
        int res =0;
        for(int i =0; i<n; i++){
            res = Math.max(res, dp1[i]+dp2[i]-1);
        }
        return res;
    }
    //二分查找，返回第一个>=x的位置
    private int bs(int[] nums, int l, int r, int x){
        while(l <= r){
            int mid = l + ((r-l)/2);
            if(nums[mid] > x){
                r = mid-1;
            }else if(nums[mid] < x){
                l = mid+1;
            }else{
                return mid;
            }
        }
        return l;
    }
}

复杂度：

时间复杂度：二分查找算法的平均时间复杂度为 $图片说明$ ,数组的大小为n，遍历一次数组，总的时间复杂度为 $图片说明$
空间复杂度：需要额外的三个数组 $dp,dp1,dp2$ ，空间复杂度为 $O(n)$