Kadane Algorithim

Kadane-Algorithim

นี่คือโซลูชัน JavaScript สำหรับหนึ่งในอัลกอริทึมการเขียนโปรแกรมแบบไดนามิกที่มีชื่อเสียงของ Algo Kadane

คำสั่งปัญหา

ได้รับอาร์เรย์ a = {a1, a2, …,} ขององค์ประกอบ n, ค้นหาผลรวมสูงสุดที่เป็นไปได้ของ a

subarray ที่ต่อเนื่องกันไม่ต่อเนื่อง (ไม่จำเป็นต้องต่อเนื่อง) subarray
ไม่ควรพิจารณา subarrays/specisions ที่ว่างเปล่า

วิดีโอ YouTube นี้โดย Ben Wright อาจเป็นประโยชน์ในการทำความเข้าใจอัลกอริทึม Kadane สำหรับ subarray สูงสุดในลำดับ 1-D

รูปแบบอินพุต

บรรทัดแรกของอินพุตมีจำนวนจำนวนเต็ม T. T ติดตาม กรณีทดสอบแต่ละกรณีเริ่มต้นด้วยจำนวนเต็ม N. ในบรรทัดถัดไปจำนวนเต็ม n ติดตามเป็นตัวแทนขององค์ประกอบของอาร์เรย์ A.

ข้อ จำกัด :

1≤t≤10
1≤n≤105
−104≤ai≤104

subarray และลำดับที่คุณพิจารณาควรมีองค์ประกอบอย่างน้อยหนึ่งองค์ประกอบ

รูปแบบเอาต์พุต

สองพื้นที่แยกจากกันจำนวนเต็มแสดงถึง subarray ที่ต่อเนื่องกันและไม่ต่อเนื่องสูงสุด ควรเลือกจำนวนเต็มอย่างน้อยหนึ่งครั้งและใส่ลงใน subarrays (อาจจำเป็นต้องใช้ในกรณีที่องค์ประกอบทั้งหมดเป็นลบ)

อินพุตตัวอย่าง

2
4
1 2 3 4
6
2 -1 2 3 4 -5

ตัวอย่างเอาต์พุต

10 10
10 11

คำอธิบาย

ในกรณีแรก: ผลรวมสูงสุดสำหรับองค์ประกอบที่ต่อเนื่องกันและไม่ต่อเนื่องคือผลรวมขององค์ประกอบทั้งหมด (เนื่องจากเป็นบวกทั้งหมด)

ในกรณีที่สอง: [2 -1 2 3 4] -> นี่เป็นรูปแบบย่อยที่ต่อเนื่องกันด้วยผลรวมสูงสุด สำหรับผลรวมสูงสุดของกลุ่มองค์ประกอบที่ไม่จำเป็นต้องพูดถึงเพียงเพิ่มองค์ประกอบเชิงบวกทั้งหมด