بزرگترین جفت لیست فرعی

برنامه نویس

امتیاز

zahranoori

255

Hoseinaj1350

217

MarsBoy (عضو ویژه)

215

user-ixnb

170

user-TT8o (عضو ویژه)

139

این تمرین قسمت دوم تمرین بزرگترین لیست فرعی است.

لیستی در ورودی داریم. هدف این مسئله یافتن لیست های فرعی (یعنی دنباله آیتم‌های مجاور) با بیشترین مجموع است.

مثلاً در لیست زیر:

[1, 6, -1, -5, -2, 5, -1, 4, -7, 1, 2, 3]

لیست فرعی که دارای حداکثر مجموع است برابر است با [5, -1, 4] که جمع آن برابر است با: 5 - 1 + 4 = 8.

قابل ذکر است، در این چالش، لیست های فرعی خالی [] را مجاز می‌کنیم که مجموع آن‌ها برابر 0 است . از این رو، برای لیستی [-4, -3, -5, -7]از اعداد منفی، فهرست فرعی [] جمع حداکثر را با مجموع 0 دارید.

تا اینجا مشابه قسمت اول بود. اما در این چالش می خواهیم جفت لیست فرعی با حداکثر مجموع، را به دست آوریم. برای مثال، برای لیست بالا، جفت لیست فرعی با حداکثر مجموع، برابرا است با [1, 6], [5, -1, 4] که دارای مجموع کل 1 + 6 + 5 - 1 + 4 = 15 است.

به عنوان مثال دیگر، برای لیست زیر:

[-1, -2, -3, 5, 4, 3, 4, 5, -9, -10]

جفت لیست فرعی با حداکثر مجموع برابر است با [5, 4, 3, 4, 5], [] با مجموع کل 5 + 4 + 3 + 4 + 5 = 21.

هدف

تابعی بنویسید که با توجه به لیستی از اعداد، مجموع کل جفت لیست فرعی با حداکثر مجموع را برمی گرداند.

مثال ها

max_sum_pair([-4, 2, -3, -2, 2, -3, 5, -2]) ➞ 7
# جفت لیست فرعی [2], [5]

نمونه ورودی و خروجی

max_sum_pair([1, 6, -1, -5, -2, 5, -1, 4, -7, 1, 2, 3]) ➞ 15

max_sum_pair([-1, -2, -3, 5, 4, 3, 4, 5, -9, -10]) ➞ 21

max_sum_pair([-4, 2, -3, -2, 2, -3, 5, -2]) ➞ 7

نکات

این مسئله را می توان به طور موثر با استفاده از الگوریتم معروف Kadane حل کرد.

self.assertEqual(max_sum_pair([1, 6, -1, -5, -2, 5, -1, 4, -7, 1, 2, 3]), 15)
self.assertEqual(max_sum_pair([-1, -2, -3, 5, 4, 3, 4, 5, -9, -10]), 21)
self.assertEqual(max_sum_pair([-4, 2, -3, -2, 2, -3, 5, -2]), 7)
self.assertEqual(max_sum_pair([0, -1, 5, -6, 5, -3, 0, -4, 5, 2, -5, 1]), 12)
self.assertEqual(max_sum_pair([-5, 3, -4, 6, 0, 0, -4, -2, -2, 7, -5, 7, -5, 5]), 15)