وصف المشكلة: صفيف مع عناصر n ، يمكن أن تكون هذه العناصر n إيجابية أو سلبية. العثور على مجموع أكبر سفر.
الطريقة 1: طريقة القوة الغاشمة
الفكرة: أسهل وأسهل طريقة للتفكير هي العثور على جميع المطلبات الفرعية ، ثم العثور على مجموع جميع البطلات الفرعية ، والحصول على أقصى قيمة في مجموع جميع المطلبات الفرعية.
/ *** الطريقة 1 (طريقة القوة الغاشمة): ابحث عن مجموع الطوائف الفرعية القصوى في حلقتين*/ static 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 ؛ }} return maxsum ؛ }الطريقة 2: البرمجة الديناميكية المحسنة
الفكرة: أولاً ، وفقًا للعلاقة بين العنصر الأخير A [N-1] من المصفوفة وأكبر جائزة فرعية ، يمكن تقسيمها إلى المواقف الثلاثة التالية:
1) يحتوي الحد الأقصى للطبقة الفرعية على [N-1] ، أي ، ينتهي بـ [N-1].
2) A [N-1] وحده يشكل أكبر سفر.
3) لا يحتوي الحد الأقصى للطبقة الفرعية على [N-1] ، لذا يمكن تحويل الحد الأقصى للطبقة الفرعية لـ A [1 ، ... ، N-1] إلى العثور على الحد الأقصى للطبقة الفرعية لـ A [1 ، ... ، N-2].
من خلال التحليل أعلاه ، يمكننا استخلاص الاستنتاج التالي: على افتراض أن مجموع مجموعة أكبر (A [0] ، ... A [I-1]) قد تم حسابها على أنها جميع [I-1] ، ويتم حساب مجموع أكبر مجموعة من [I-1] في (A [0] ، ... A [A-1]) على النحو [I-1].
ثم يمكن الحصول على العلاقة التالية: جميع [i-1] = max {a [i-1] ، end [i-1] ، all [i-1]}. استخدم هذه الصيغة وفكرة البرمجة الديناميكية لحل المشكلات. (الرمز يحل أيضًا مشكلة موضع البدء ووضع النهاية)
/*** الطريقة 2: طريقة البرمجة الديناميكية المحسنة* يتم الحصول على الحاديقة عن طريق إضافة صفائف إلى [i] بالتسلسل ، ثم مقارنتها مع [i] "، وحفظ العدد الأكبر. لأنه إذا تمت إضافة الرقم السابق إلى السجل [i]* ليس ككل [i] نفسه ، فإن العدد السابق لن يكون له أي مساهمة في الجزء الأكبر. int static int max (int m ، int n) {return m> n؟ m: n ؛ Max (Max+A [i] ، A [i]) ؛ maxsum = integer.min_value ؛ int nstart = 0 ؛ لـ (int i = 0 ؛ i <a.length ؛ i ++) {if (nsum <0) {nsum = a [i] ؛ nstart = i ؛ } آخر {nsum+= a [i] ؛ } if (nsum> maxsum) {maxsum = nsum ؛ ابدأ = nstart ؛ نهاية = أنا ؛ }} return maxsum ؛ }ما سبق هو كل محتوى هذه المقالة. آمل أن يكون محتوى هذه المقالة من بعض المساعدة في دراسة أو عمل الجميع. آمل أيضًا دعم wulin.com أكثر!