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

华一仙

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

1. from time import perf_counter  # 单位为秒
   
2. 
   
3. def cal_time(func):
   
4.     """ 懒人测时间 """
   
5.     def inn(nums):
   
6.         start = perf_counter()
   
7.         res = func(nums)
   
8.         stop = perf_counter()
   
9.         print(f">>> result = {res}, run time: {(stop - start) * 1000}ms")
   
10.     return inn
    
11. 
    
12. @cal_time
    
13. def f266(nums):
    
14.     size = len(nums)
    
15.     if size < 2:
    
16.         return None  # 以防万一，就是不知道该返回 None 还是 False
    
17. 
    
18.     minL = [0] * size
    
19.     maxL = [0] * size
    
20.     minL[0] = maxL[0] = nums[0]
    
21.     for i in range(1, size):
    
22.         minL[i] = min(minL[i-1] + nums[i], nums[i])  # minL[i] 存放 nums[:i+1] 的切片的最小值，其余三个同理
    
23.         maxL[i] = max(maxL[i-1] + nums[i], nums[i])
    
24. 
    
25.     minR = [0] * size
    
26.     maxR = [0] * size
    
27.     minR[-1] = maxR[-1] = nums[-1]
    
28.     for i in range(size - 2, -1, -1):
    
29.         minR[i] = min(minR[i+1] + nums[i], nums[i])
    
30.         maxR[i] = max(maxR[i+1] + nums[i], nums[i])
    
31. 
    
32.     res = float("-inf")
    
33.     for i in range(size - 1):
    
34.         res = max(res, abs(maxL[i] - minR[i + 1]), abs(minL[i] - maxR[i + 1]))
    
35.     return res
    
36. 
    
37. if __name__ == "__main__":
    
38.     arr1 = [-2, 0, 0, 1, -1, -1]  # 3
    
39.     arr2 = [-5, -4]  # 1
    
40.     arr3 = [1, 2, -3, 1]  # 6
    
41. 
    
42.     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

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

1. def fun266(n):
   
2.     max_pre = max_cur = float('-inf')
   
3.     min_pre = min_cur = float('+inf')
   
4.     for i in n:
   
5.         max_cur = max(max_cur + i, i)        
   
6.         max_pre = max(max_pre, max_cur)        
   
7.         min_cur = min(min_cur + i, i)
   
8.         min_pre = min(min_pre, min_cur)        
   
9.     return max_pre - min_pre

复制代码

kinkon

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

检查居然是错误的，晕倒