الگوریتم زیردنباله

[taghiv]

با سلام
سوال اینه
فرض کنید آرایه ای از n عدد صحیح داریم ، می خواهیم بزرگترین زیردنباله از این اعداد را از نظر مجموع آنها بدست آوریم
اگر تمامی اعداد منفی باشند جواب صفر خواهد بود
مثلاً اگر آرایه این باشد:





-2,11,-4,13,-5,-6,6




جواب این خواهد بود:


11,-4,13



الگوریتم پیشنهادی و پیچیدگی آن را ارائه دهید (از تقسیم و غلبه استفاده شود)

[مسعود اقدسی فام]

این مساله رو با مرتبه n^2 می‌شه حل کرد. ولی تقسیم و غلبه بحثش جداست.

[taghiv]

خب بفرمایید حلشو.

[مسعود اقدسی فام]

خب بفرمایید حلشو.


http://www.algorithmha.ir (http://www.algorithmha.ir/post-%D9%85%D8%B3%D8%A7%D9%84%D9%87-%D8%AD%D8%AF%D8%A7%DA%A9%D8%AB%D8%B1-%D9%85%D8%AC%D9%85%D9%88%D8%B9.aspx)


این مطلب رو بخونید. مشابه همین حل می‌شه.

البته شاید راه دیگه‌ای هم داشته باشه.

[taghiv]

این که فقط یه شبه کده ! هیچ توضیحی هم نداده که چطور به این شبه کد رسیده
جواب بهتری سراغ ندارید؟

[مسعود اقدسی فام]

این که فقط یه شبه کده ! هیچ توضیحی هم نداده که چطور به این شبه کد رسیده
جواب بهتری سراغ ندارید؟

چون می‌خواستم خواننده خودش کمی زحمت کد نوشتن رو بکشه کد رو نذاشتم. وگرنه کد کامل تست شده و جواب گرفته. این هم که اون رابطه (و نه شبه کد) از کجا اومده وحی نیست. یه رابطه ریاضیه که خیلی راحت می‌شه اثبات کرد.

کد نابهینه به طور کامل نوشته شده. زحمت کد بهینه با توجه به توضیحاتی که داده شده با خودتون. اگه نمی‌تونید بنویسید دیگه بحث الگوریتم نیست. باید روی تبدیل الگوریتم به کد و برنامه‌نویسی کار کنید.

در ضمن این مساله برای ماتریس و زیرماتریس بیشینه در فضای دو بعدیه. باید رابطه رو کمی تغییر بدید تا به آرایه خطی تبدیل بشه.

[taghiv]

خب پس این یه رابطه و فرموله. یعنی تنها نکته ی اون شبه کد ، یه رابطه ست.
من فکر نمی کنم این جوابی باشه که من دنبالشم .
من فقط یه دانشجوی ساده کارشناسی ناپیوسته هستم و تو درس ما هیچ نوع فرمولی تا حالا اثبات نشده
حتی اگه اینو یاد بگیرم ، و برای آرایه عادی قابل استفاده باشه ، استاد ازم قبول نمی کنه.

خودم این جواب رو بدست آوردم:

ورودی: آرایه so به طول n
خروجی : ماتریس ans به اندازه n*n که پاسخ ، بزرگترین عنصر این ماتریس است.

برای پر کردن ماتریس


for i=1 to n

ans[i,i]=so[i]

for(i=1 to n-1)

for(j=i+1 to n)

ans[i,j]=ans[i,j-1]+so[j]



مثال:
ورودی:


1-,5,7,-3,2,-9

خروجی:

88240

نشون میده که دو تایی دوم ما (5و7) که عدد 12 رو در خانه 2،3 بوجود آورده ، بزرگترین زیررشته مونه.
مرتبه ی اجراییش هم اگه درست حساب کرده باشم میشه:


(n-1)^2)/2

[مسعود اقدسی فام]

خب پس این یه رابطه و فرموله. یعنی تنها نکته ی اون شبه کد ، یه رابطه ست.
من فکر نمی کنم این جوابی باشه که من دنبالشم .
من فقط یه دانشجوی ساده کارشناسی ناپیوسته هستم و تو درس ما هیچ نوع فرمولی تا حالا اثبات نشده
حتی اگه اینو یاد بگیرم ، و برای آرایه عادی قابل استفاده باشه ، استاد ازم قبول نمی کنه.

خودم این جواب رو بدست آوردم:

ورودی: آرایه so به طول n
خروجی : ماتریس ans به اندازه n*n که پاسخ ، بزرگترین عنصر این ماتریس است.

برای پر کردن ماتریس


for i=1 to n

ans[i,i]=so[i]

for(i=1 to n-1)

for(j=i+1 to n)

ans[i,j]=ans[i,j-1]+so[j]



مثال:
ورودی:


1-,5,7,-3,2,-9

خروجی:

88240

نشون میده که دو تایی دوم ما (5و7) که عدد 12 رو در خانه 2،3 بوجود آورده ، بزرگترین زیررشته مونه.
مرتبه ی اجراییش هم اگه درست حساب کرده باشم میشه:


(n-1)^2)/2


من که گفتم از مرتبه N ^ 2 حل می‌شه و راهی هم که نشون دادم تنها راه نیست.

البته اون رابطه هم بیان دیگه‌ای از همین روشیه که شما استفاده کردید. ولی در کل مهم نیست. به هر حال همین که جواب رو به دست آوردید خیلی خوبه. موفق باشید.