[已解决]Python：每日一题 266

华一仙

答题之前，先感谢一下抽时间出题、判题的版主，以及提供过题目的鱼友们
原来“不重叠”是指“两个切片的索引没有交集”

from time import perf_counter  # 单位为秒

def cal_time(func):
    """ 懒人测时间 """
    def inn(nums):
        start = perf_counter()
        res = func(nums)
        stop = perf_counter()
        print(f">>> result = {res}, run time: {(stop - start) * 1000}ms")
    return inn

@cal_time
def f266(nums):
    size = len(nums)
    if size < 2:
        return None  # 以防万一，就是不知道该返回 None 还是 False

    minL = [0] * size
    maxL = [0] * size
    minL[0] = maxL[0] = nums[0]
    for i in range(1, size):
        minL[i] = min(minL[i-1] + nums[i], nums[i])  # minL[i] 存放 nums[:i+1] 的切片的最小值，其余三个同理
        maxL[i] = max(maxL[i-1] + nums[i], nums[i])

    minR = [0] * size
    maxR = [0] * size
    minR[-1] = maxR[-1] = nums[-1]
    for i in range(size - 2, -1, -1):
        minR[i] = min(minR[i+1] + nums[i], nums[i])
        maxR[i] = max(maxR[i+1] + nums[i], nums[i])

    res = float("-inf")
    for i in range(size - 1):
        res = max(res, abs(maxL[i] - minR[i + 1]), abs(minL[i] - maxR[i + 1]))
    return res

if __name__ == "__main__":
    arr1 = [-2, 0, 0, 1, -1, -1]  # 3
    arr2 = [-5, -4]  # 1
    arr3 = [1, 2, -3, 1]  # 6

    f266(arr3)

zltzlt

华一仙 发表于 2019-11-2 08:13
答题之前，先感谢一下抽时间出题、判题的版主，以及提供过题目的鱼友们
原来“不重叠”是指“两个切片的索 ...

恭喜通过！

执行用时：152 ms

阴阳神万物主

我20楼题目预订成没成功？楼主，给个信儿啊。

zltzlt

阴阳神万物主 发表于 2019-11-2 11:37
我20楼题目预订成没成功？楼主，给个信儿啊。

因为此题不是原创的，所以不成功。

阴阳神万物主

zltzlt 发表于 2019-11-2 12:21
因为此题不是原创的，所以不成功。

哦，好吧

kinkon

只是为了完成作业，过程大概懂，速度应该算这个最优了

def fun266(n):
    max_pre = max_cur = float('-inf')
    min_pre = min_cur = float('+inf')
    for i in n:
        max_cur = max(max_cur + i, i)        
        max_pre = max(max_pre, max_cur)        
        min_cur = min(min_cur + i, i)
        min_pre = min(min_pre, min_cur)        
    return max_pre - min_pre

kinkon

kinkon 发表于 2019-12-31 10:27
只是为了完成作业，过程大概懂，速度应该算这个最优了

检查居然是错误的，晕倒