(۱۱ خرداد ۱۳۹۵ ۰۲:۳۴ ق.ظ)behnam5670 نوشته شده توسط:  

(11 خرداد ۱۳۹۵ ۰۱:۴۱ ق.ظ)kamal3401 نوشته شده توسط:  سلام من رو این سوال زیاد فکر کردم ولی به جوابی نرسیدم میشه راهنمایی کنید؟

فرض کنید ارایه ای از n عدد صحیح داریم میخوایهم بزرگترین زیر دنباله از این اعداد را از نظر مجموع انها بدست اوریم
اگر تمامی اعداد منفی باشند جواب صفر خواهد بود! پیچیدگی الگوریتم پیشنهادی را با روش تقسیم و غلبه محاسبه کنید

برای نمونه در دنباله ی $\opencurlybrace-2\: ,\: 11\: ,-4\: ,\: 13\: ,-5\: ,\: 4\: ,-6\closecurlybrace$ جواب $\opencurlybrace\: 11\: ,-4\: ,\: 13\closecurlybrace$ 20 خواهد بود

عنصر وسطی آرایه رو در نظر بگیرید. زیر رشته‌ی ماکزیمم (جواب مسأله) ممکن هست دارای این عنصر باشه، ممکن هم هست نباشه.
۱) اگر زیر رشته‌ی ماکزیمم فاقد عنصر وسطی باشه، پس باید زیر رشته‌ی ماکزیمم رو در نصفه‌ی چپ و نصفه‌ی راست بگردیم.
۲) اما اگر زیر رشته‌ی ماکزیمم، دارای عنصر وسطی بود، پی باید منتهی الیه سمت چپ زیر رشته (یعنی اولین عنصر زیر رشته‌ی ماکزیمم) رو از نیمه‌ی سمت چپ بگردیم، عنصر آخر (سمت راست‌ترین عنصر) رو هم از نیمه‌ی سمت راستی بگردیم.

پس ۳ تا چیز رو پیدا میکنیم و بزرگترین اون ۳ چیز رو به عنوان جواب مسأله برمیگردونیم:
۱) بزرگترین زیررشته‌ی نیمه‌ی چپ اعداد
۲) بزرگترین زیررشته‌ی نیمه‌ی راست اعداد
فرض میکنیم عنصر وسطی هم در زیر رشته‌ی ماکزیمم هست، پس ۳) زیررشته‌ای که عنصر وسطی هم داخلش هست و کران پایینش رو طوری از نیمه‌ی چپ انتخاب میکنیم که اعداد نیمه‌ی چپ ماکزیمم باشند، کران بالاش رو هم از نیمه‌ی راست طوری انتخاب میکنیم که اون اعداد هم ماکزیمم بشه جمعش.
شبه کدش یه همچین چیزی میشه:

کد:

int maxSub(int left, int right){
   if(left == right)
      return a[left];
   int mid = (left + right)/2;
   int left_ans = maxSub(left, mid);
   int right_ans = maxSub(mid + 1, right);
   int left_max = a[mid];
   int right_max = a[mid + 1];
   int sum = 0;
   for(int i = mid; i >= left; i--){
      sum = sum + a[i];
      if(sum > left_max)
         left_max = sum;
   }
   sum = 0;
   for(int i = mid + 1; i <= right; i++){
      sum = sum + a[i];
      if(sum > right_max)
         right_max = sum;
   }
   return max(left_ans, right_ans, left_max + right_max);  
}

(۱۱ خرداد ۱۳۹۵ ۰۲:۴۰ ق.ظ)kamal3401 نوشته شده توسط:  

(11 خرداد ۱۳۹۵ ۰۲:۳۴ ق.ظ)behnam5670 نوشته شده توسط:  

(11 خرداد ۱۳۹۵ ۰۱:۴۱ ق.ظ)kamal3401 نوشته شده توسط:  سلام من رو این سوال زیاد فکر کردم ولی به جوابی نرسیدم میشه راهنمایی کنید؟

فرض کنید ارایه ای از n عدد صحیح داریم میخوایهم بزرگترین زیر دنباله از این اعداد را از نظر مجموع انها بدست اوریم
اگر تمامی اعداد منفی باشند جواب صفر خواهد بود! پیچیدگی الگوریتم پیشنهادی را با روش تقسیم و غلبه محاسبه کنید

برای نمونه در دنباله ی $\opencurlybrace-2\: ,\: 11\: ,-4\: ,\: 13\: ,-5\: ,\: 4\: ,-6\closecurlybrace$ جواب $\opencurlybrace\: 11\: ,-4\: ,\: 13\closecurlybrace$ 20 خواهد بود

عنصر وسطی آرایه رو در نظر بگیرید. زیر رشته‌ی ماکزیمم (جواب مسأله) ممکن هست دارای این عنصر باشه، ممکن هم هست نباشه.
۱) اگر زیر رشته‌ی ماکزیمم فاقد عنصر وسطی باشه، پس باید زیر رشته‌ی ماکزیمم رو در نصفه‌ی چپ و نصفه‌ی راست بگردیم.
۲) اما اگر زیر رشته‌ی ماکزیمم، دارای عنصر وسطی بود، پی باید منتهی الیه سمت چپ زیر رشته (یعنی اولین عنصر زیر رشته‌ی ماکزیمم) رو از نیمه‌ی سمت چپ بگردیم، عنصر آخر (سمت راست‌ترین عنصر) رو هم از نیمه‌ی سمت راستی بگردیم.

پس ۳ تا چیز رو پیدا میکنیم و بزرگترین اون ۳ چیز رو به عنوان جواب مسأله برمیگردونیم:
۱) بزرگترین زیررشته‌ی نیمه‌ی چپ اعداد
۲) بزرگترین زیررشته‌ی نیمه‌ی راست اعداد
فرض میکنیم عنصر وسطی هم در زیر رشته‌ی ماکزیمم هست، پس ۳) زیررشته‌ای که عنصر وسطی هم داخلش هست و کران پایینش رو طوری از نیمه‌ی چپ انتخاب میکنیم که اعداد نیمه‌ی چپ ماکزیمم باشند، کران بالاش رو هم از نیمه‌ی راست طوری انتخاب میکنیم که اون اعداد هم ماکزیمم بشه جمعش.
شبه کدش یه همچین چیزی میشه:

کد:

int maxSub(int left, int right){
   if(left == right)
      return a[left];
   int mid = (left + right)/2;
   int left_ans = maxSub(left, mid);
   int right_ans = maxSub(mid + 1, right);
   int left_max = a[mid];
   int right_max = a[mid + 1];
   int sum = 0;
   for(int i = mid; i >= left; i--){
      sum = sum + a[i];
      if(sum > left_max)
         left_max = sum;
   }
   sum = 0;
   for(int i = mid + 1; i <= right; i++){
      sum = sum + a[i];
      if(sum > right_max)
         right_max = sum;
   }
   return max(left_ans, right_ans, left_max + right_max);  
}

خیلی ممنون توضیحات خیلی عالی بود
پیچیدگی زمانیشو هم میشه رابطه بازگشتیشو فقط بگید؟
پس ما سه تا زیر مسئله داریم؟