ปัญหาอาเรย์ย่อยสูงสุดจะเหมือนกับปัญหาสไลซ์สูงสุด บทช่วยสอนนี้กล่าวถึงปัญหาของการเข้ารหัสใน C++ คำถามคือ ผลรวมสูงสุดของลำดับตัวเลขที่ต่อเนื่องกันภายในอาร์เรย์คือเท่าใด นี่อาจหมายถึงอาร์เรย์ทั้งหมด ปัญหานี้และวิธีแก้ไขในภาษาใดๆ เรียกว่า ปัญหาอาร์เรย์ย่อยสูงสุด อาร์เรย์สามารถมีตัวเลขติดลบได้
การแก้ปัญหาจะต้องมีประสิทธิภาพ จำเป็นต้องมีความซับซ้อนของเวลาที่เร็วที่สุด ณ ตอนนี้ อัลกอริธึมที่เร็วที่สุดสำหรับการแก้ปัญหาเป็นที่รู้จักในชุมชนวิทยาศาสตร์ว่าอัลกอริทึมของ Kadane บทความนี้อธิบายอัลกอริทึมของ Kadane ด้วย C++
ตัวอย่างข้อมูล
พิจารณาเวกเตอร์ (อาร์เรย์):
เวกเตอร์ < int > เอ = { 5 , - 7 , 3 , 5 , - สอง , 4 , - 1 } ;
สไลซ์ (อาร์เรย์ย่อย) ที่มีผลรวมสูงสุดคือลำดับ {3, 5, -2, 4} ซึ่งให้ผลรวมเป็น 10 ไม่มีลำดับอื่นใดที่เป็นไปได้ แม้แต่อาร์เรย์ทั้งหมด จะให้ผลรวมสูงถึง ค่า 10 ทั้งอาร์เรย์ให้ผลรวมเป็น 7 ซึ่งไม่ใช่ผลรวมสูงสุด
พิจารณาเวกเตอร์ต่อไปนี้:
เวกเตอร์ < int > ข = { - สอง , 1 , - 3 , 4 , - 1 , สอง , 1 , - 5 , 4 } ;
สไลซ์ (อาร์เรย์ย่อย) ที่มีผลรวมสูงสุดคือลำดับ {4, -1, 2, 1} ซึ่งให้ผลรวมเป็น 6 โปรดทราบว่าอาจมีตัวเลขติดลบภายในอาร์เรย์ย่อยสำหรับผลรวมสูงสุด
พิจารณาเวกเตอร์ต่อไปนี้:
เวกเตอร์ < int > ค = { 3 , สอง , - 6 , 4 , 0 } ;
สไลซ์ (อาร์เรย์ย่อย) ที่มีผลรวมสูงสุดคือลำดับ {3, 2} ซึ่งให้ผลรวมเป็น 5
พิจารณาเวกเตอร์ต่อไปนี้:
เวกเตอร์ < int > ด = { 3 , สอง , 6 , - 1 , 4 , 5 , - 1 , สอง } ;
อาร์เรย์ย่อยที่มีผลรวมสูงสุดคือลำดับ {3, 2, 6, -1, 4, 5, -1, 2} ซึ่งให้ผลรวมเป็น 20 เป็นอาร์เรย์ทั้งหมด
พิจารณาเวกเตอร์ต่อไปนี้:
เวกเตอร์ < int > อี = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , สิบห้า , 4 , - 8 , - สิบห้า , - 22 } ;
มีอาร์เรย์ย่อยสองอาร์เรย์ที่มีผลรวมสูงสุดที่นี่ ผลรวมที่สูงกว่าคือสิ่งที่ถือเป็นวิธีแก้ปัญหา (คำตอบ) สำหรับปัญหาอาร์เรย์ย่อยสูงสุด อาร์เรย์ย่อยคือ: {5, 7} มีผลรวม 12 และ {6, 5, 10, -5, 15, 4} ที่มีผลรวม 35 แน่นอนว่าสไลซ์ที่มีผลรวม 35 คือ คำตอบ.
พิจารณาเวกเตอร์ต่อไปนี้:
เวกเตอร์ < int > ฉ = { - 4 , 10 , สิบห้า , 9 , - 5 , - ยี่สิบ , - 3 , - 12 , - 3 , 4 , 6 , 3 , สอง , 8 , 3 , - 5 , - สอง } ;
มีสองอาร์เรย์ย่อยที่มีผลรวมสูงสุด ผลรวมที่สูงกว่าคือสิ่งที่ถือเป็นวิธีแก้ปัญหาสำหรับปัญหาอาร์เรย์ย่อยสูงสุด อาร์เรย์ย่อยคือ: {10, 15, 9} ที่มีผลรวม 34 และ {4, 6, 3, 2, 8, 3} ที่มีผลรวม 26 แน่นอนว่าสไลซ์ที่มีผลรวม 34 คือ คำตอบเพราะปัญหาคือการมองหาอาร์เรย์ย่อยที่มีผลรวมสูงสุดไม่ใช่อาร์เรย์ย่อยที่มีผลรวมสูงกว่า
การพัฒนาอัลกอริทึมของ Kadane
ข้อมูลในบทช่วยสอนนี้ไม่ใช่งานต้นฉบับจาก Kadane เป็นวิธีการสอนอัลกอริทึมของ Kadane ของผู้เขียนเอง หนึ่งในเวกเตอร์ด้านบนที่มียอดรวมวิ่งอยู่ในตารางนี้:
| ข้อมูล | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | สิบห้า | 4 | -8 | -สิบห้า | -22 |
| วิ่งทั้งหมด | 5 | 12 | 8 | -สอง | -8 | -สอง | 3 | 13 | 8 | 23 | 27 | ยี่สิบเอ็ด | 16 | -6 |
| ดัชนี | 0 | 1 | สอง | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | สิบเอ็ด | 12 | 13 |
การรัน Total สำหรับดัชนีคือผลรวมของค่าก่อนหน้าทั้งหมดรวมทั้งค่าสำหรับดัชนี มีสองลำดับที่มีผลรวมสูงสุดที่นี่ คือ {5, 7} ซึ่งให้ผลรวม 12 และ {6, 5, 10, -5, 15, 4} ซึ่งให้ผลรวมเป็น 35 ลำดับที่ให้ผลรวม 35 คือสิ่งที่ต้องการ .
สังเกตว่าสำหรับยอดรวมที่กำลังรัน มีพีคสองค่าคือค่า 12 และ 27 พีคเหล่านี้สอดคล้องกับดัชนีสุดท้ายของสองลำดับ
ดังนั้น แนวคิดของอัลกอริธึมของ Kadane คือการทำยอดรวมในขณะที่เปรียบเทียบผลรวมสูงสุดตามที่พบ โดยย้ายจากซ้ายไปขวาในอาร์เรย์ที่กำหนด
เวกเตอร์อื่นจากด้านบนพร้อมผลรวมที่วิ่งอยู่ในตารางนี้:
มีสองลำดับที่มีผลรวมสูงสุด พวกมันคือ {10, 15, 9} ซึ่งให้ผลรวม 34; และ {4, 6, 3, 2, 8, 3} ซึ่งให้ผลรวมเป็น 26 ลำดับที่ให้ผลรวม 34 คือสิ่งที่ต้องการ
สังเกตว่าสำหรับยอดรวมที่รันอยู่ มีพีคสองค่าคือค่า 30 และ 13 พีคเหล่านี้สอดคล้องกับดัชนีสุดท้ายของสองลำดับ
อีกครั้ง แนวคิดของอัลกอริธึมของ Kadane คือการทำยอดรวมในขณะที่เปรียบเทียบผลรวมสูงสุดตามที่พบ โดยย้ายจากซ้ายไปขวาในอาร์เรย์ที่กำหนด
รหัสโดยอัลกอริทึมของ Kadane ใน C++
รหัสที่ให้ไว้ในส่วนนี้ของบทความไม่จำเป็นต้องเป็นรหัสที่ Kadane ใช้ อย่างไรก็ตามมันเป็นโดยอัลกอริทึมของเขา โปรแกรมเช่นเดียวกับโปรแกรม C++ อื่นๆ จะเริ่มต้นด้วย:
#include#include<เวกเตอร์>
ใช้เนมสเปซ std;
มีการรวมไลบรารี iostream ซึ่งรับผิดชอบอินพุตและเอาต์พุต ใช้เนมสเปซมาตรฐาน
แนวคิดของอัลกอริธึมของ Kadane คือการมียอดรวมขณะเปรียบเทียบผลรวมสูงสุดตามที่พบ โดยย้ายจากซ้ายไปขวาในอาร์เรย์ที่กำหนด ฟังก์ชันสำหรับอัลกอริทึมคือ:
int maxSunArray ( เวกเตอร์ < int > & อา ) {int N = A.size ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
สำหรับ ( int ผม = 1 ; ผม < ยังไม่มีข้อความ; ฉัน++ ) {
int tempRunTotal = runTotal + A [ ผม ] ; // อาจเล็กกว่า A [ ผม ]
ถ้า ( อา [ ผม ] > tempRunTotal )
runTotal = A [ ผม ] ; // ใน กรณี อา [ ผม ] มากกว่าการวิ่งทั้งหมด
อื่น
runTotal = tempRunTotal;
ถ้า ( runTotal > maxAmount ) // เปรียบเทียบผลรวมสูงสุดทั้งหมด
maxSum = runTotal;
}
กลับ จำนวนเงินสูงสุด;
}
ขนาด N ของอาร์เรย์ที่กำหนด (เวกเตอร์) ถูกกำหนด ตัวแปร maxSum เป็นหนึ่งในผลรวมสูงสุดที่เป็นไปได้ อาร์เรย์มีผลรวมสูงสุดอย่างน้อยหนึ่งรายการ ตัวแปร runTotal แสดงถึงยอดรวมที่รันในแต่ละดัชนี ทั้งคู่เริ่มต้นด้วยค่าแรกของอาร์เรย์ ในอัลกอริธึมนี้ ถ้าค่าถัดไปในอาร์เรย์มากกว่าผลรวมการทำงาน ค่าถัดไปนั้นจะกลายเป็นผลรวมการทำงานใหม่
มีหนึ่งวงหลักสำหรับวง การสแกนเริ่มต้นจาก 1 และไม่ใช่ศูนย์เนื่องจากการเริ่มต้นของตัวแปร maxSum และ runTotal ถึง A[0] ซึ่งเป็นองค์ประกอบแรกของอาร์เรย์ที่กำหนด
ใน for-loop คำสั่งแรกจะกำหนดยอดรวมชั่วคราวโดยการเพิ่มมูลค่าปัจจุบันเข้ากับผลรวมสะสมของค่าก่อนหน้าทั้งหมด
ต่อไปมีโครงสร้าง if/else หากค่าปัจจุบันเพียงอย่างเดียวมากกว่าผลรวมที่รันอยู่ ค่าเดียวนั้นจะกลายเป็นผลรวมรัน สิ่งนี้มีประโยชน์โดยเฉพาะอย่างยิ่งหากค่าทั้งหมดในอาร์เรย์ที่กำหนดเป็นค่าลบ ในกรณีนี้ ค่าลบสูงสุดเพียงอย่างเดียวจะกลายเป็นค่าสูงสุด (คำตอบ) หากค่าปัจจุบันเพียงอย่างเดียวไม่มากกว่าผลรวมการรันชั่วคราวจนถึงตอนนี้ ผลรวมการรันจะกลายเป็นยอดรวมการรันก่อนหน้าบวกกับค่าปัจจุบัน ซึ่งเป็นส่วนอื่นของโครงสร้าง if/else
ส่วนโค้ดสุดท้ายใน for-loop จะเลือกระหว่างผลรวมสูงสุดก่อนหน้าสำหรับลำดับก่อนหน้า (อาร์เรย์ย่อย) และผลรวมสูงสุดในปัจจุบันสำหรับลำดับปัจจุบัน ค่าที่สูงกว่าจึงถูกเลือก สามารถมีผลรวมอาร์เรย์ย่อยสูงสุดได้มากกว่าหนึ่งรายการ โปรดทราบว่ายอดรวมจะเพิ่มขึ้นและลดลง เนื่องจากอาร์เรย์ถูกสแกนจากซ้ายไปขวา มันตกลงมาตามค่าลบ
ผลรวมของอาร์เรย์ย่อยสูงสุดที่เลือกสุดท้ายจะถูกส่งคืนหลัง for-loop
เนื้อหาสำหรับฟังก์ชันหลัก C++ ที่เหมาะสม สำหรับฟังก์ชันอัลกอริทึมของ Kadane คือ:
เวกเตอร์ < int > เอ = { 5 , - 7 , 3 , 5 , - สอง , 4 , - 1 } ; // { 3 , 5 , - สอง , 4 } - > 10int ret1 = maxSunArray ( อา ) ;
ศาล << ret1 << ปลาย;
เวกเตอร์ < int > ข = { - สอง , 1 , - 3 , 4 , - 1 , สอง , 1 , - 5 , 4 } ; // { 4 , − 1 , สอง , 1 } - > 6
int ret2 = maxSunArray ( บี ) ;
ศาล << ret2 << ปลาย;
เวกเตอร์ < int > ค = { 3 , สอง , - 6 , 4 , 0 } ; // { 3 , สอง } - > 5
int ret3 = maxSunArray ( ค ) ;
ศาล << ret3 << ปลาย;
เวกเตอร์ < int > ด = { 3 , สอง , 6 , - 1 , 4 , 5 , - 1 , สอง } ; // { 3 , สอง , 6 , - 1 , 4 , 5 , - 1 , สอง } - > 5
int ret4 = maxSunArray ( ดี ) ;
ศาล << net4 << ปลาย;
เวกเตอร์ < int > อี = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , สิบห้า , 4 , - 8 , - สิบห้า , - 22 } ; // { 6 , 5 , 10 , - 5 , สิบห้า , 4 } - > 35
int ret5 = maxSunArray ( และ ) ;
ศาล << ret5 << ปลาย;
เวกเตอร์ < int > ฉ = { - 4 , 10 , สิบห้า , 9 , - 5 , - ยี่สิบ , - 3 , - 12 , - 3 , 4 , 6 , 3 , สอง , 8 , 3 , - 5 , - สอง } ; // { 10 , สิบห้า , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
ศาล << ขวา 6 << ปลาย;
ด้วยเหตุนี้ผลลัพธ์จะเป็น:
10
6
5
ยี่สิบ
35
3. 4
แต่ละบรรทัดตอบที่นี่ สอดคล้องกับอาร์เรย์ที่กำหนดตามลำดับ
บทสรุป
ความซับซ้อนของเวลาสำหรับอัลกอริทึมของ Kadane คือ O(n) โดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์ที่กำหนด ความซับซ้อนในเวลานี้เป็นวิธีที่เร็วที่สุดสำหรับปัญหา sub-array สูงสุด มีอัลกอริธึมอื่นที่ช้ากว่า แนวคิดของอัลกอริธึมของ Kadane คือการทำยอดรวมในขณะที่เปรียบเทียบผลรวมสูงสุดตามที่พบ โดยย้ายจากซ้ายไปขวาในอาร์เรย์ที่กำหนด หากค่าปัจจุบันเพียงอย่างเดียวมากกว่าผลรวมที่รันอยู่ ค่าเดียวนั้นจะกลายเป็นผลรวมรันใหม่ มิฉะนั้น ยอดรวมรันใหม่คือยอดรวมการรันก่อนหน้าบวกอิลิเมนต์ปัจจุบัน ตามที่คาดไว้ เมื่อสแกนอาร์เรย์ที่ระบุ
สามารถมีผลรวมสูงสุดได้มากกว่าหนึ่งรายการ สำหรับอาร์เรย์ย่อยที่แตกต่างกัน เลือกผลรวมสูงสุดสูงสุดสำหรับอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมด
ดัชนีจำกัดสำหรับช่วงของผลรวมสูงสุดที่เลือกคืออะไร – นั่นคือการสนทนาในบางครั้ง!
คริส