8.23饿了么笔试

第二题： 一个数组的权值是最大值减最小值

给一个数组，你可以切分成若干个子数组，求最大权值和

样例：[1,1,4,3,5] 输出7

from functools import lru_cache
import math
a = [1, 1, 4, 3, 5]
@lru_cache(None)
def dfs(i: int) -> int:
    res = 0
    for j in range(i):
        min_val = min(a[j: i+1])
        max_val = max(a[j: i+1])
        # print(min_val, max_val)
        res = max(res, dfs(j - 1) + max_val - min_val)
        # print(res)
    return res
print(dfs(len(a) - 1))

今晚没参加 自己试了一下可以过第一个样例 #饿了么笔试#