این سوال: یکی substring داریم یکی subsequence که اینجا به نظر من اولی میشه.

حالا چطور عمل کنیم؟ اول دوتا متغییر داریم یکی max کلی و دیگری max محلی اول کار یکیش -۱ و دیگری ۰ هست. حالا از اول ارایه شروع میکنیم و عنصر اول رو که دیدیم محلی رو یکی زیاد میکنیم و عنصر بعدی رو نگاه میکنیم اگه بزرگتر بود که محلی رو یکی دوباره افزایش میدیم اگه نه که این محلی رو با کلی مقایسه میکنیم هر کدوم بزرگتر بود انتخابش می کنیم، و در اینجا محلی رو صفر میکنیم چون دیگه صعودی نیست، همین جوری تا آخر پیش میریم.

اگه زیردنباله منظورش بود یه راه حل n2 داره به این صورت که یه آرایه کمکی میگیریم و اونو با یک مقدار دهی میکنیم و معنیش این میشه که بزرگترین زیر دنباله ای که به این عنصر ختم میشه و از خونه شماره j شروع میکنیم و چک میکنیم که آیا واسه i هایی که از j کوچترن زیر دنباله ای که به i ختم میشه رو میتونیم تا j ادامه بدیم؟ که این زمانی اتفاق میافته که a[j] x از a[i] x بزرگتر باشه(ایکس ها الکین) که در اینصورت ما خونه مربوطه در j رو به a[i] + 1 x تغییر میدیم (البته اگه از مقدار قبلی j بزرگ تر بود !) که اینم کلن میشه n2 ولی یه راه حل nlgn هم داره که الان یادم نیست.

(۱۴ بهمن ۱۳۹۲ ۰۸:۱۶ ب.ظ)Good! نوشته شده توسط:  سلام دوستان.کمک
فکر میکنم این سوال منظورش از زیردنباله متوالی اینه که بدون وقفه عناصر پشت سر هم بیان ولی تعریفی که برای زیر دنباله متوالی داده رو متوجه نمیشم.
جواب گزینه ۴ هست.یعنی اینطوری که از اول دنباله شروع میکنیم دونه دونه میریم جلو تا زمانیکه دیگه اکیدا صعودی نباشه.اونوقت نقطه شروع رو با طول زیر دنباله ۱جا ذخیره میکنیم و نقطه بعدی رو برای شروع در نظر میگیریم.آخر سر هم بزرگترین طول رو انتخاب میکنیم.درسته؟
حالا اگه نیازی نباشه بدون وقفه بیان چی؟راه حل پویا داره؟
ممنونم از همه

راه حلی که خودتون گفتید درسته.
برای پیدا کردن بزرگترین زیر دنباله (مجموعه اعداد زیر دنباله حداکثر باشه) راه حل پویا داریم تو کتاب clrs توضیح داده
من حدس می زنم برای این که با اون قاطی کنیم این پویا رو هم داده شاید هم راه حل پویا هم داشته باشه!!!

(۱۴ بهمن ۱۳۹۲ ۰۸:۲۵ ب.ظ)mehdi.m2 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۰۸:۱۶ ب.ظ)Good! نوشته شده توسط:  سلام دوستان.کمک
فکر میکنم این سوال منظورش از زیردنباله متوالی اینه که بدون وقفه عناصر پشت سر هم بیان ولی تعریفی که برای زیر دنباله متوالی داده رو متوجه نمیشم.
جواب گزینه ۴ هست.یعنی اینطوری که از اول دنباله شروع میکنیم دونه دونه میریم جلو تا زمانیکه دیگه اکیدا صعودی نباشه.اونوقت نقطه شروع رو با طول زیر دنباله ۱جا ذخیره میکنیم و نقطه بعدی رو برای شروع در نظر میگیریم.آخر سر هم بزرگترین طول رو انتخاب میکنیم.درسته؟
حالا اگه نیازی نباشه بدون وقفه بیان چی؟راه حل پویا داره؟
ممنونم از همه

راه حلی که خودتون گفتید درسته.
برای پیدا کردن بزرگترین زیر دنباله (مجموعه اعداد زیر دنباله حداکثر باشه) راه حل پویا داریم تو کتاب clrs توضیح داده
من حدس می زنم برای این که با اون قاطی کنیم این پویا رو هم داده شاید هم راه حل پویا هم داشته باشه!!!

خیلی ممنونم ازتون
ینی اگه بدون وقفه هم نیان بازم راه حل پویا داره؟
ببخشید میشه لطف کنید بگید این تعریفی که سوال داده اصن چی هست؟b-a ینی چی؟

---

(۱۴ بهمن ۱۳۹۲ ۰۸:۲۵ ب.ظ)mehdi.m2 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۰۸:۱۶ ب.ظ)Good! نوشته شده توسط:  سلام دوستان.کمک
فکر میکنم این سوال منظورش از زیردنباله متوالی اینه که بدون وقفه عناصر پشت سر هم بیان ولی تعریفی که برای زیر دنباله متوالی داده رو متوجه نمیشم.
جواب گزینه ۴ هست.یعنی اینطوری که از اول دنباله شروع میکنیم دونه دونه میریم جلو تا زمانیکه دیگه اکیدا صعودی نباشه.اونوقت نقطه شروع رو با طول زیر دنباله ۱جا ذخیره میکنیم و نقطه بعدی رو برای شروع در نظر میگیریم.آخر سر هم بزرگترین طول رو انتخاب میکنیم.درسته؟
حالا اگه نیازی نباشه بدون وقفه بیان چی؟راه حل پویا داره؟
ممنونم از همه

راه حلی که خودتون گفتید درسته.
برای پیدا کردن بزرگترین زیر دنباله (مجموعه اعداد زیر دنباله حداکثر باشه) راه حل پویا داریم تو کتاب clrs توضیح داده
من حدس می زنم برای این که با اون قاطی کنیم این پویا رو هم داده شاید هم راه حل پویا هم داشته باشه!!!

خیلی ممنونم ازتون
ینی اگه بدون وقفه بیان(همین سوال) بازم راه حل پویا داره؟حالا اگه بدون وقفه نیان چی؟ینی مثلا یکی در میون هم بتونن بیان.
ببخشید میشه لطف کنید بگید این تعریفی که سوال داده اصن چی هست؟b-a ینی چی؟

با lcs ان به توان ۲
با تقسیم غلبه ان لاگ ان
با یک روش پویا ان
جواب این سواله
اما نمی دونم جزئیات روش پویاش و تقسیم غلبش چیه
منظورش از متوالی دقیقا پشت سر هم نیست بکه طوریه که ترتیب به هم نخوره این مطلب را شرط زیر میگه هر هر a ای که خاصیت صعودی بودن را به هم میزنه از دنباله بی حذفش کن
B.bj-aj-i

اما
سوال اینجاست که اگر قرارB را طبق الگوی بالا بسازیم هم باید i را بشماریم هم j را اقل کمش باید یه ان به توان دو داشته باشم چرا جواب میشه ان

منم خیلی برام سوال شده این مساله...دوستان کسی نیست توضیحی داشته باشه ؟!

سلام
ببخشید من هم نفهمیدم اول اینکه منظور سوال این بود که زیر دنباله از اعضای پشت سر هم a باشه یا نه فقط ترتیب در این مجموعه رعایت شده باشه؟

اگر باید پشت سر هم باشند که واضحه اوردر ان میشه، ولی اگه پشت سر هم نباشه چطور باید حل کنیم و چه مرتبه ای داره؟

سلام....
چون یکی از بچه ها گفتن این سوالو از دکتر یوسفی بپرسم همین الان از ایشون از طریق تلفن پرسیدم:
گفتن چند الگوریتم واسه این کار وجود داره که بهترینش الگوریتم پویاست و یه چیزی تو مایه های الگوریتم کاتود برش میله هست که باید یه آرایه واسش در نظر گرفت و به صورت بازگشتی روی خونه هاش بازگشت کرد.هر خونه آرایه با تتا ۱ میشه به دستش آورد و کلش چون n تا خونست با تتا n می شه به دست آورد.

موفق باشید....

(۱۶ بهمن ۱۳۹۲ ۱۰:۰۰ ب.ظ)mahsalove نوشته شده توسط:  سلام....
چون یکی از بچه ها گفتن این سوالو از دکتر یوسفی بپرسم همین الان از ایشون از طریق تلفن پرسیدم:
گفتن چند الگوریتم واسه این کار وجود داره که بهترینش الگوریتم پویاست و یه چیزی تو مایه های الگوریتم کاتود برش میله هست که باید یه آرایه واسش در نظر گرفت و به صورت بازگشتی روی خونه هاش بازگشت کرد.هر خونه آرایه با تتا ۱ میشه به دستش آورد و کلش چون n تا خونست با تتا n می شه به دست آورد.

موفق باشید....

بسی دستتون درد نکنه
ینی الان این سوال منظورش از متوالی "بدون وقفه پشت سر هم اومدن" نیست؟
کاش یکی از دوستان هم لطف میکرد این برش میله رو توضیح میداد

(۱۶ بهمن ۱۳۹۲ ۱۰:۰۰ ب.ظ)mahsalove نوشته شده توسط:  سلام....
چون یکی از بچه ها گفتن این سوالو از دکتر یوسفی بپرسم همین الان از ایشون از طریق تلفن پرسیدم:
گفتن چند الگوریتم واسه این کار وجود داره که بهترینش الگوریتم پویاست و یه چیزی تو مایه های الگوریتم کاتود برش میله هست که باید یه آرایه واسش در نظر گرفت و به صورت بازگشتی روی خونه هاش بازگشت کرد.هر خونه آرایه با تتا ۱ میشه به دستش آورد و کلش چون n تا خونست با تتا n می شه به دست آورد.

موفق باشید....

الگوریتم برش لوله من یادمه که n به توان دو بود نه n چون هر بار کل آرایه ی پر شده تا اون خونه چک می شد

---

(۲۰ بهمن ۱۳۹۲ ۰۲:۲۷ ق.ظ)Riemann نوشته شده توسط:  این سوال: یکی substring داریم یکی subsequence که اینجا به نظر من اولی میشه.

حالا چطور عمل کنیم؟ اول دوتا متغییر داریم یکی max کلی و دیگری max محلی اول کار یکیش -۱ و دیگری ۰ هست. حالا از اول ارایه شروع میکنیم و عنصر اول رو که دیدیم محلی رو یکی زیاد میکنیم و عنصر بعدی رو نگاه میکنیم اگه بزرگتر بود که محلی رو یکی دوباره افزایش میدیم اگه نه که این محلی رو با کلی مقایسه میکنیم هر کدوم بزرگتر بود انتخابش می کنیم، و در اینجا محلی رو صفر میکنیم چون دیگه صعودی نیست، همین جوری تا آخر پیش میریم.

اگه زیردنباله منظورش بود یه راه حل n2 داره به این صورت که یه آرایه کمکی میگیریم و اونو با یک مقدار دهی میکنیم و معنیش این میشه که بزرگترین زیر دنباله ای که به این عنصر ختم میشه و از خونه شماره j شروع میکنیم و چک میکنیم که آیا واسه i هایی که از j کوچترن زیر دنباله ای که به i ختم میشه رو میتونیم تا j ادامه بدیم؟ که این زمانی اتفاق میافته که a[j] x از a[i] x بزرگتر باشه(ایکس ها الکین) که در اینصورت ما خونه مربوطه در j رو به a[i] + 1 x تغییر میدیم (البته اگه از مقدار قبلی j بزرگ تر بود !) که اینم کلن میشه n2 ولی یه راه حل nlgn هم داره که الان یادم نیست.

منم با تو موافقم منظور substring هست که خیلی راحت میشه n