机器学习与数据挖掘-1

1.给你一个数列，要求你构造一个新数列，新数列里每一个值小于原数列的值且大于deng1，让abs(A[i]- A[i-1])的总值最大，比如 10 2 10 2 10，你可以构建10 1 10 1 10，输出值为36（滴滴出行）

参考答案
简单的思路是递归，给定序列[a_0, a_1, a_2, ..., a_k]，假设新数列前i-1个数值已经构建好了，那么我们要决策是下一个数值i要不要改成1，还是保留原值
那么就变成了比较
[b_0, b_1, b_{i-1}, a_i, con(剩下的a, a_i)]
和
[b_0, b_1, b_{i-1}, 1, con(剩下的a, 1)]

所以我们可以用递归的思路来完成

def con(x, previous_number=None):
    # 输入是原始序列的话，那么最左边的比较对象设为自己就好
    # 这样可以保证不会对要不要改成1的结果有所影响
    if previous_number is None:
        previous_number = x[0]
    k = len(x)
    if k == 1:
        # 只剩一个元素了，那就比较下是保留原值好
        # 还是变成1比较好
        if abs(1 - previous_number) > abs(x[0] - previous_number):
            x[0] = 1
        v = abs(x[0] - previous_number)
    else:
        # 有多个元素
        # 算一下保留原值带来的增益是多少
        x1_remaining, v1_remaining = con(x[1:], x[0])
        v1 = abs(x[0] - previous_number) + v1_remaining

        # 算一下改为1带来的增益是多少
        x2_remaining, v2_remaining = con(x[1:], 1)
        v2 = abs(1 - previous_number) + v2_remaining

        # 改为1有利可图，把当前子数列的第一个元素改为1
        # 然后接着往后判断
        if v1 < v2:
            v = v2
            x[0] = 1
            x_remaining = x2_remai