小红书5月7日算法笔试编程题

第二问是个脑筋急转弯，不是典型的算法题。时间复杂度和空间复杂度都是 O(n)。

现有 n 个整数 a1, ..., an，每次操作可以删除一段下标连续的数字（例如 a2, a3, a4），但删除后剩余的整数个数必须大于 0。请进行最多 k 次这样的操作，使得最后剩余的整数中的最小值最大，并将这个最大的最小值输出。（1≤n,k≤10^5）

输入数据有两行，为

n k

a1 ... an

以下为一个样例

输入：

5 1

58 63 61 89 57

输出：

58

对问题的空间进行合理划分是本题的关键：

1. 当 k > 1 时，只要找到最大值所在位置，并将两侧的片段删除即可，这样剩下的就是全局最大值。
2. 当 k = 1 时，如果删除中间的一段子列，那么剩下的片段为 [头1, ..., 尾1] 和 [头2, ..., 尾2]，有如下关系

min⁡([头1,...,尾1])≤头1

min⁡([头2,...,尾2])≤尾2

min⁡(剩下的片段)≤max⁡(头1,尾2)

而目标函数的上界（不等式的右侧） max⁡(头1,尾2) 可以通过一次切割（保留最左的头1，或保留最右的尾2）实现，因此切中间的子片段一定不优于仅保留 a1​,an​ 中的最大值，同样可以发现保留左侧或保留右侧也一定不优于仅保留 a1, an​ 中的最大值。 代码如下

n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
if k > 1:
	print(max(a))
else:
	print(max(a[0], a[-1])