Lập Trình Viên Số Khổ
Senior Member
subs là dãy hiệu
remain_arr là dãy loại bỏ số 0 từ dãy hiệu
=> kết quả = từ dãy hiệu ta cần tìm các đoạn âm dương xen kẽ dài nhất có thể
gọi f là kết quả khi kết thúc tại i
khi trái dấu thì f[i+1] = f + 1
còn cùng dấu thì không thay đổi f[i+1] = f
remain_arr là dãy loại bỏ số 0 từ dãy hiệu
=> kết quả = từ dãy hiệu ta cần tìm các đoạn âm dương xen kẽ dài nhất có thể
gọi f là kết quả khi kết thúc tại i
khi trái dấu thì f[i+1] = f + 1
còn cùng dấu thì không thay đổi f[i+1] = f
Python:
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums) == 1:
return 1
subs = [nums[i] - nums[i-1] for i in range(1, len(nums))]
remain_arr = []
count_zero = 0
for sub in subs:
if sub == 0:
count_zero += 1
continue
remain_arr.append(sub)
if len(remain_arr) <= 1:
return len(nums) - count_zero
f = [0] * len(remain_arr)
for i in range(len(remain_arr)-1):
if remain_arr[i] * remain_arr[i+1] >= 0:
f[i+1] = f[i] + 1
else:
f[i+1] = f[i]
return len(nums) - f[len(remain_arr)-1] - count_zero
Last edited: