الحد الأقصى لمجموع التبعية :مارك فايس:

Question

في الجزء المميز أدناه، كيف يستنتج فايس أن المصفوفة التي تبدأ عند فهرس عشوائي "p" وتنتهي عند "j" لا يمكن أبدًا أن تكون أكبر من المصفوفة التي تبدأ عند "i" وتنتهي عند "p-1"؟

من خلال مثاله الخاص (الحلقة الداخلية للخوارزمية 2 الموضحة أدناه) فإن هذا خطأ واضح.

دع i = 0، و j = 3.

افترض أن [ 0 ] = -14، أ[ 1 ] = -4، أ[ 2 ] = -2، أ[ 3 ] = -1.

إذا كانت p = 2، فمن الواضح أن مجموع التسلسل من "p" إلى "j" أكبر من "i" إلى "p-1".

والأكثر إثارة للقلق هو السيد.يبدو أن فايس يسحب افتراضًا من لا شيء ("j هو المؤشر الأول الذي يتسبب في أن تصبح التسلسل اللاحق بدءًا من المؤشر i سلبيًا") في حين أنه لا يوجد شيء مما سبق يمكن أن يشير إلى ذلك!في الواقع، يذكر فايس فقط أن "اكتشاف" مجموع التسلسل سالب بين الفهرس "i" و"j"، ولكن لم يذكر أبدًا المكان الذي يمكن أن يحدث فيه مصدر هذا فقط.من أين يأتي هذا؟

شكرا على اي مساعدة!

Answer 1

أعتقد أنك في حيرة من أمرك بشأن الخوارزمية التي يصفها.وصفه ليس للخوارزمية 2 ولكن للخوارزمية 4، حيث يوجد فهرس وهمي i في إعادة تقديم.

اسمحوا لي أن أكتب هذه الخوارزمية مع هذا الفهرس لأوضح لك:

maxSubSum(array a):
  maxSum = 0, thisSum = 0;
  i = 0;
  for j going from 0 to length(a)-1:
    thisSum += a[j];
    if thisSum > maxSum:
      maxSum = thisSum;
    else if thisSum < 0:
      i = j+1;
      thisSum = 0;
   return maxSum;

الآن يمكنك أن ترى ذلك في هذه الخوارزمية، عندما يكون هذا المجموع <0، إذن j هو بالفعل "الفهرس الأول الذي يسبب التسلسل اللاحق بدءًا من الفهرس i لتصبح سلبية"، ويتبع بقية الادعاء.لاحظ على وجه الخصوص أن المثال الذي قدمته لا يمكن أن يحدث مع هذه الخوارزمية (لن يكون لديك أبدًا i=0 و j=3 في هذه الحالة).