โปรแกรมหาผลรวมสูงสุดของ subarray modulo โดย m ใน Python
สมมติว่าเรามีจำนวนอาร์เรย์ที่มีองค์ประกอบ n เรามีจำนวนเต็ม m อีกตัว เราต้องหาค่าสูงสุดของผลรวมของ subarray modulo m.
ดังนั้น หากอินพุตเท่ากับ nums =[1,5,7,3] m =5 เอาต์พุตจะเป็น 3 เพราะ
- [1] mod 5 =1
- [5] mod 5 =0
- [7] mod 5 =2
- [3] mod 5 =3
- [1,5] mod 5 =1
- [5,7] mod 5 =2
- [7,3] mod 5 =0
- [1,5,7] mod 5 =3
- [5,7,3] mod 5 =0
- [1,5,7,3] mod 5 =1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- csum :=รายการและเริ่มแทรก nums[0] mod m ลงในนั้น
- สำหรับแต่ละ x เป็น nums ยกเว้นค่าแรก do
- แทรก (รายการสุดท้ายของ csum + x) mod m ที่ส่วนท้ายของ csum
- เห็น :=รายการที่มีองค์ประกอบเดียวในตอนแรกที่เป็น 0
- max_sum :=-1
- สำหรับแต่ละ s ใน csum ทำ
- idx :=ตำแหน่งซ้ายสุดที่จะแทรก s เข้าไปให้เห็น เพื่อที่รายการจะถูกจัดเรียง
- ถ้า idx <ขนาดที่เห็นแล้ว
- max_sum :=สูงสุดของ max_sum และ s
- มิฉะนั้น
- แทรก s ที่ดัชนีด้านซ้ายสุดของการมองเห็นเพื่อให้จัดเรียงอาร์เรย์
- แทรก s ที่ดัชนีด้านซ้ายสุดของการมองเห็นเพื่อให้จัดเรียงอาร์เรย์
- ส่งคืน max_sum
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
import bisect def solve(nums, m): csum = [nums[0] % m] for x in nums[1:]: csum.append((csum[-1] + x) % m) seen = [0] max_sum = -1 for s in csum: idx = bisect.bisect_left(seen, s) if idx < len(seen): max_sum = max(max_sum, s, (s - seen[idx]) % m) else: max_sum = max(max_sum, s) bisect.insort_left(seen, s) return max_sum nums = [1,5,7,3] m = 5 print(solve(nums, m))
อินพุต
"pptpp", [(1,1),(1,4),(1,1),(0,2)]
ผลลัพธ์
3
