คำอธิบายปัญหา: อาร์เรย์ที่มีองค์ประกอบ n องค์ประกอบ n เหล่านี้อาจเป็นบวกหรือลบ ค้นหาผลรวมของ subarray ที่ใหญ่ที่สุด
วิธีการที่ 1: วิธีการเดรัจฉาน
แนวคิด: วิธีที่ง่ายที่สุดและง่ายที่สุดในการคิดคือการค้นหา subarrays ทั้งหมดจากนั้นค้นหาผลรวมของ subarrays ทั้งหมดและรับค่าสูงสุดในผลรวมของ subarrays ทั้งหมด
/ *** วิธีการ 1 (วิธีการบังคับ Brute): ค้นหาผลรวมของ subarrays สูงสุดในสองลูป*/ สาธารณะ int maxsubarray1 (int [] a) {int i, j; int thissum = 0; int maxsum = 0; สำหรับ (i = 0; i <a.length; i ++) {thissum = a [i]; สำหรับ (j = i+1; j <a.length; j ++) {thissum+= a [j]; if (thissum> maxsum) {maxsum = thissum; }} ส่งคืน maxsum; -วิธีที่ 2: การเขียนโปรแกรมแบบไดนามิกที่ดีที่สุด
แนวคิด: ประการแรกตามความสัมพันธ์ระหว่างองค์ประกอบสุดท้าย [N-1] ของอาร์เรย์และ subarray ที่ใหญ่ที่สุดมันสามารถแบ่งออกเป็นสามสถานการณ์ต่อไปนี้:
1) subarray สูงสุดมี [N-1] นั่นคือลงท้ายด้วย [N-1]
2) A [N-1] เพียงอย่างเดียวเป็น subarray ที่ใหญ่ที่สุด
3) subarray สูงสุดไม่มี [N-1] ดังนั้นการค้นหา subarray สูงสุดของ [1, ... , n-1] สามารถแปลงเพื่อค้นหา subarray สูงสุดของ [1, ... , n-2]
ผ่านการวิเคราะห์ข้างต้นเราสามารถวาดข้อสรุปต่อไปนี้: สมมติว่าผลรวมของอาร์เรย์ที่ใหญ่ที่สุดของ (A [0], ... A [I-1]) ได้รับการคำนวณเป็น [I-1] ทั้งหมดและผลรวมของอาร์เรย์ที่ใหญ่ที่สุดของ [I-1] ใน (A [0], ... A [I-1])
จากนั้นความสัมพันธ์ต่อไปนี้สามารถรับได้: ทั้งหมด [i-1] = สูงสุด {a [i-1], สิ้นสุด [I-1], ทั้งหมด [I-1]} ใช้สูตรนี้และแนวคิดของการเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหา (รหัสยังแก้ปัญหาของตำแหน่งเริ่มต้นและตำแหน่งสิ้นสุด)
/** * วิธีที่ 2: วิธีการเขียนโปรแกรมแบบไดนามิกที่เหมาะสม * ได้รับโดยการเพิ่มอาร์เรย์ลงใน [i] ตามลำดับจากนั้นเปรียบเทียบกับ [i] "และบันทึกที่ใหญ่กว่าเพราะถ้าหมายเลขก่อนหน้านี้ไม่ได้มีขนาดใหญ่ ก่อนหน้า*/สาธารณะ int max (int m, int n) {return m> n? m: n;} สาธารณะ int maxsubarray2 (int [] a) {int nall = a [0]; i ++) {nend = max (nend+a [i], a [i]); maxsum = integer.min_value; int nstart = 0; สำหรับ (int i = 0; i <a.length; i ++) {ถ้า (nsum <0) {nsum = a [i]; nstart = i; } else {nsum+= a [i]; } if (nsum> maxsum) {maxsum = nsum; เริ่มต้น = nstart; สิ้นสุด = i; }} ส่งคืน maxsum; -ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่าเนื้อหาของบทความนี้จะช่วยในการศึกษาหรือทำงานของทุกคน ฉันหวังว่าจะสนับสนุน Wulin.com เพิ่มเติม!