สมมติว่าเรามีอาร์เรย์บाइनารี nums เราสามารถลบอิลิเมนต์หนึ่งได้ เราต้องหาขนาดของ subarray ที่ไม่ว่างและประกอบด้วย 1 เท่านั้นที่ยาวที่สุดในอาร์เรย์ที่เหลือ ถ้าไม่มีให้คืน 0
เช่น ถ้าข้อมูลเข้าเป็น nums = [1,0,1,1,1,0,1,1,0] ผลลัพธ์จะเป็น 5 เพราะลบ 0 ตำแหน่ง 5 (0-indexed) จะได้ subarray [1,1,1,1,1] ยาว 5
ขั้นตอนการแก้ปัญหา
- ถ้าไม่มี 0 ใน nums: คืน len(nums) - 1 (ต้องลบ 1 ตัว)
- ถ้าไม่มี 1 ใน nums: คืน 0
- สร้างลิสต์ a โดยบีบอัดกลุ่ม 1 ติดต่อกันและ 0 สลับกัน:
- cnt = 0
- วนลูป i ใน nums:
- ถ้า i == 0: ถ้า cnt > 0 ใส่ cnt เข้า a, cnt = 0; ใส่ 0 เข้า a
- มิฉะนั้น: cnt += 1
- ถ้า cnt > 0 ใส่ cnt เข้า a
- Max = 0
- วนลูปดูตำแหน่งที่เป็น 0 ใน a:
- ถ้า 0 อยู่ปลาย: Max = max(Max, ค่าที่อยู่ข้างเคียง)
- ถ้า 0 อยู่กลาง: Max = max(Max, ค่าซ้าย + ค่าขวา)
- คืนค่า Max
ตัวอย่างโค้ด
def solve(nums):
if 0 not in nums:
return len(nums) - 1
if 1 not in nums:
return 0
a = []
cnt = 0
for i in nums:
if i == 0:
if cnt != 0:
a.append(cnt)
cnt = 0
a.append(i)
else:
cnt += 1
if cnt != 0:
a.append(cnt)
Max = 0
for i in range(len(a)):
if a[i] != 0:
continue
if a[i] == 0 and i == len(a) - 1:
Max = max(Max, a[i-1])
elif a[i] == 0 and i == 0:
Max = max(Max, a[i+1])
elif a[i] == 0:
Max = max(Max, a[i+1] + a[i-1])
return Max
nums = [1,0,1,1,1,0,1,1,0]
print(solve(nums))
ข้อมูลเข้า
[1,0,1,1,1,0,1,1,0]
ข้อมูลออก
5
