این مسئله رو به روشای مختلفی میشه حل کرد. ولی بذارین با روشایی که تا الان کار کردیم حلشون کنیم :
عضو i ام آرایه ی b مساویه با جمع همه ی عضوای a تو بازه ی بسته 1 تا i . و b0 = 0 هستش.
برای اینکه بدونیم مسئلن از کتاب سوم تا ششم چقد باید بخونیم میتونیم اینجوری بنویسیم :
sum = b[6] - b[3-1] = b[6] - b[2]
حالا برای پیدا کردن جواب... هر دفعه یه کتاب رو بعنوان کتاب اول فرض میکنیم و با جستجوی دودیی تو کتابای بعد از خودش دنبال جواب مناسب میگردیم و جواب ماکسیمم رو انتخاب میکنیم . O_nlogn
اما میشه با O_n هم مسئله رو حل کرد. میتونید کدش رو ببینید :
تو این روش میایم دو تا اشاره گر میگیریم که x به کتاب اول اشاره میکنه و اشاره گر دوم یعنی y اونقدر میره جلو که جمع زمانها از t بیشتر نشه و بهترین جواب رو برای موقعی که x اولین کتاب باشه پیدا میکنه .
بعد میایم x رو از مجموعه حذف میکنیم و تعدادش رو از sum کم میکنیم و میریم سراغ کتاب بعدی و همین کار رو ادامه میدیم ...
ولی y رو به اول برنمیگردونیم چون میدونیم وقتی x رو از مجموعه حذف میکنیم sum کمتر میشه و امکان نداره تا اون نقطه sum برای کتاب جدید بیشتر از t بشه پس حتما تا اونجارو میتونیم بخونیم .
پس ما از روی هر کتاب با اشاره گرای xوy فقط یبار رد میشیم که میشه 2n = O_n
