الحد الأقصى SUBAIRIY SUM

Question

هذا سؤال من خوارزميات الكتاب من قبل جيف إريكسون.

لنفترض أن مجموعة دائرية. في هذا الإعداد، يمكن أن يكون "ضميزي متجاور" إما فاصل زمني [i .. j] أو لاحقة تليها بادئة A [i .. n] · [1 .. J]. صف وتحليل الخوارزمية التي تجد ضميزة متجاورة من أكبر مبلغ. تتكون مجموعة الإدخال من أرقام حقيقية.

نهجي:

هناك اثنين من الاحتمالات

1.) لا التفاف حولها (يمكننا استخدام خوارزمية كادان)

2.) التفاف حولها (أي؛ مؤشر بدء الضوئي أكبر من فهرس النهاية) (لدي شك في هذه الحالة)

الآن إرجاع الحالتين كحد أقصى نتيجة لذلك.

للحصول على الحالة الثانية، قدم البحث على الإنترنت نهج دون إثبات.

النهج هو العثور على ضمادات مع الحد الأدنى من المبلغ وطرحه من مجموع الصفيف بأكمله (أي Sum (a) - min_subarray_sum (a)). كيف يتم تصحيح هذا الحل؟

رابط للطريقة المستخدمة في الحالة الثانية: https:// www. geeksforgeeks.org/maximum-contiguous-circular-sum/

Answer 1

دع $ $ تكون صفيفك، دع $ B $ subariay دائري من $ $ تزيد $ \ sum_ {b \ in b} b $ ، واسمحوا $ C $ يكون subarray يحتوي على جميع عناصر $ $ التي ليست في $ B $ . لاحظ أن $ c $ هي أيضا ضميزة دائرية.

لديك $ \ sum_ {a \ in a} a=sum_ {b \ in b + sum_ {c \ in c} c $ ، مما يعني أن $ \ sum_ {c \ in c} c=sum_ {a \ in a} a - \ sum_ {b \ in b} b $ . منذ $ \ sum_ {a \ in a} $ هو ثابت (WRT $ B $ ) و $ B $ تعظيم $ \ sum_ {b \ in b} b $ ، $ C $ يقلل $ \ sum_ {c \ in c} c $ .

علاوة على ذلك، واحد على الأقل من $ B $ و $ C $ ليس فقط دائريا ولكن أيضا متجاورة وبالتالي يمكن العثور عليها في $ O (n) $ الوقت.