Guest User

Untitled

a guest
Dec 17th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.72 KB | None | 0 0
  1. '''
  2. 子数组的取值范围
  3. Description
  4. 给定数组arr和整数num,求arr的连续子数组中满足:
  5. 其最大值减去最小值的结果大于num的个数。请实现一
  6. 个时间复杂度为O(length(arr))的算法。
  7.  
  8. Input
  9. 输入的第一行为数组,每一个数用空格隔开,第二行为num。
  10.  
  11. Output
  12. 输出一个值。
  13.  
  14. Sample Input 1
  15. 3 6 4 3 2
  16. 2
  17.  
  18. Sample Output 1
  19. 6
  20. '''
  21. #这里复杂度不是O(lengh(arr))
  22. def subArr(arr,num):
  23. n = 0
  24. for i in range(len(arr)):
  25. if i == len(arr) - 1:
  26. break
  27. for j in range(i+1,len(arr)):
  28. if max(arr[i:j+1])-min(arr[i:j+1]) > num:
  29. n +=1
  30. return n
  31. arr = list(map(int,input().split()))
  32. num = int(input())
  33. print(subArr(arr,num))
Add Comment
Please, Sign In to add comment