P90.3 SlalomSkiing
Given a sequence, find the longest subsequence that can be decomposed into at most three monotonic parts.
-
P90.3 障碍滑雪
给定一个序列,找出最多可分解为三个单调部分的最长子序列
一个参加障碍滑雪的运动员。滑雪跑道位于一个斜坡上,并且两侧用栅栏围起来。跑道上设置有N个障碍门。每个障碍门的位置都垂直于斜坡顶部的起始线。 每个障碍门与起始线、右栅栏(从起始线向下看时的右方)的距离都不同。可以从起始线上的任何地方出发,滑下赛道,尽可能多地通过障碍门,最终到达终点线。 通过障碍门意味着要滑过障碍门的位置。
开始滑时可以从两个方向滑下:向左或向右。当运动员滑到左边时,会通过与右栅栏的距离较大的障碍门,当滑到右边时,会通过与右边栅栏的距离较小的障碍门。开始滑动的方向固定为向左。
需要说明的是,频繁改变方向(从左到右或从右到左)是不被允许的的,规定运动员整个滑雪过程中最多改变两次方向。目标是计算经过最多两次方向的变化,通过障碍门的最大数量。障碍门的设置由N个整数组成的数组A给出,数组的元素指定了障碍门的位置: (0 ≤ K < N)号障碍门与起跑线的距离为K+1,与右边栅栏的距离为A[K]。
例如,考虑数组A,其中N=13:
A[0] = 15,A[1] = 13,A[2] = 5,A[3] = 7,A[4] = 4,A[5] = 10,A[6] = 12,A[7] = 8,A[8] = 2,A[9] = 11,A[10] = 6, A[11] = 9,A[12] = 3
上图数组A中记录的障碍门的位置和一条经过8个障碍门的路线的示例轨迹。开始后,向左滑雪(从运动员的角度),经过2、3、5、6号障碍门,然后向右改变方向。 在那之后,可以经过7号门,8号障碍门,然后向左转。最后,经过10号,11号障碍门,到达终点线完成整个过程。最多经过两次方向的变化,无法通过更多的门,因此8是最大值。
编写函数:
def solution(A)
给定一个由N个整数组成的数组A,则返回可以通过的最大障碍门数。例如,针对上面的示例,函数应该返回8。对于数组A:A[0]=1, A[1]=5,应返回2。
假定:
- N是区间[1,100,000]内的整数;
- 数组A的每个元素都是区间[1,1,000,000,000]内的整数;
- 数组A的元素都是不同的;
- 解题思路
对于给定的数组A,其实本题要解决的是:三个连续(所谓连续,就是前一个序列的最后一个元素就是后一个序列的第一个元素)的单调序列中包含元素的最大个数。并且开头和结尾都是递增序列,中间的是递减序列。假设对于数组A而言,下图绿色线段所示的序列为满足条件的最大序列:
image如上图所示,黑色的点代表原始数据中的但不是满足条件的序列中的点。绿色实线上的点为满足条件的序列中的点。红色虚线上的点为数组转换后的对应点。上图描述的是,将原始数组经过转换,把原始数组中的递增、递减、递增序列转变为递增序列。然后再针对得到的数组计算最大递增子序列,从而得到最终的答案。现在的问题是如果进行转换,而不会影响最终的结果。下面给出一种方式:
首先考虑中间的递减序列,因为递减变递增,肯定要将原来递减的数变为其相反数,也就是数组A中的元素S,变为-S,此外这个序列要大于第一个递增序列中的元素。假设数组A的元素最大值为M,M+M-S>=S肯定成立,因此M+M-S可看作一种转换。考虑到最后的递增序列,M+M+S>=M+M-S肯定成立,所以M+M+S也是一种转换。所以遍历数组A中的元素S,首先添加M+M+S,然后添加M+M-S,最后添加S构成新的数组B,然后针对B计算最大递增子序列。之所以先添加M+M+S,是因为所求的是递增序列,后加的话会影响结果。
关于计算最大递增子序列有2种算法,分别是时间复杂度为O(N*logN)的基于二分查找+动态规划的算法的和时间复杂度为O(N**2)的单纯的动态规划算法。
- Python3代码
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 90:Tasks from Indeed Prime 2015 challenge
# P 90.3 SlalomSkiing
def longest_increasing_subsequence_dp(a):
"""
利用动态规划算法,计算最长的递增子序列
时间复杂度o(N**2)
:param a: 数组a
:return: 最长递增子序列的长度
"""
length = len(a)
save_max = [1] * length
for i in range(1, length):
for j in range(i):
if a[i] > a[j] and save_max[j] + 1 > save_max[i]:
save_max[i] = save_max[j] + 1
return max(save_max)
def longest_increasing_subsequence_bs(a):
"""
利用二分查找算法+动态规划,计算最长的递增子序列
时间复杂度o(N*logN)
:param a: 数组a
:return: 最长递增子序列的长度
"""
num_list = [-1, a[0]] # 添加-1是为了二分查找的时候,要保证num_list[j-1]是存在的
for i in a[1:]:
if i > num_list[-1]:
num_list.append(i)
elif i < num_list[-1]: # 使用二分查找算法,在num_list查找第一个不小于i的数,并替换之
# 也就是寻找使得num_list[j-1] < i,并且num_list[j] >= i的j,然后令num_list[j] = i
# 注意数组a中可能存在相同的元素
start = 0
end = len(num_list) - 1
sign = 0
middle = 0
while start <= end:
middle = int((start + end) / 2)
if num_list[middle] < i:
start = middle + 1
elif num_list[middle] > i:
end = middle - 1
else:
sign = 1 # 恰好相等的时候
break
if sign:
num_list[middle] = i
else:
num_list[start] = i
return len(num_list) - 1
def solution(A):
"""
给定数组,找出最多可分解为三个单调部分的最长子序列
:param A: 数组
:return: 三个单调部分的最长子序列
"""
max_num = max(A) # 数组trans中会存在相同的元素
trans = []
for i in A:
trans.append(max_num + max_num + i)
trans.append(max_num + max_num - i)
trans.append(i)
return longest_increasing_subsequence_bs(trans)
点击获得更多编程练习题。欢迎Follow,感谢Star!!! 扫描关注微信公众号pythonfan,获取更多。
image image
网友评论