动态规划

这里跟以往不一样的是，需要注意一下上升子序列的定义，这里的子序列可以是间断的，这就加大了这个问题的难度。

我们用动态规划来解决这个问题，定义数组dp，长度与输入数组nums保持一致，dp[i]所代表的含义是以nums[i]结尾的所有上升子序列的最大长度。例如在数组[1, 7, 2, 3, 4, 9]中，[1, 2, 3, 9]为一个到9的上升子序列，[1, 7, 9]也是一个到9的上升子序列，但是前者更长。

定义初始状态，以dp[i]（0<=i<len(nums)）结尾的所有上升子序列最短是1，也就是只有它本身。

递归关系式：为了求得到达数组中特定位置dp[i]的最长上升子序列的长度，我们需要考虑到在此之前的所有最长上子序列，也就是dp[i]的计算需要依据dp[j]（j<=0<i）的计算结果，因此需要两重循环。为了确保子序列是上升的，需要随时判断dp[i]和dp[j]之间的关系。dp[i]的位置随时更新为当前最长子序列的长度。递推关系式为：

dp[i] = max(dp[i], dp[j]+1)，条件是 nums[j] < nums[i]

为什么dp[j]+1可以算作到达dp[i]的一个上升子序列的长度？因为当nums[i]<nums[i]时，nums[i]的元素相当于对nums[j]结尾的最长上升子序列的一个扩展。为什么需要取max?因为到达nums[i]的上升子序列不止一个，需要取最长的。

最终结果：由于我们并不知道最长上升子序列在什么位置结尾，因此需要对dp中所有元素取最大值。

作者：玖月晴 链接：https://www.jianshu.com/p/ff887a93437d 来源：简书 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

遗憾的是，经常超时，可能还是需要用二分法做，方式我没看懂

import sys


# 获取最大增长子序列
def get_max_up_sub_arr(count, arr):
    up_arr = [1 for x in range(count)]
    for i in range(count):
        for j in range(i):
            if arr[j] < arr[i]:
                up_arr[i] = max(up_arr[i], up_arr[j]+1)
    return up_arr


while True:
    try:
        count = int(input())
        arr = list(map(int, input().split(' ')))
        left_up_arr = get_max_up_sub_arr(count, arr)
        right_up_arr = get_max_up_sub_arr(count, arr[::-1])[::-1]
        print(count - max(i + j - 1 for i, j in zip(left_up_arr, right_up_arr)))
    except EOFError:
        break