در این پست میخوایم یکی دیگر از سوال های مربوط به مسابقات برنامه نویسی مانند acm رو مطرح کنیم.
شرح کلی سوال به این صورت که شما یک آرایه n عضوی رو دریافت میکنید . حال باید ماکزیمم ترین مجموع ممکن [i*arr[i برای این این آرایه پیدا کنید.حال فرض کنید آرایه زیر رو داریم :

{arr[] = {8, 3, 1, 2

تمام چرخش های [i*arr[i ممکن برای این آرایه میشه :

و ماکزیمم بین این ها هم میشه 29 . پس خروجی این ورودی میشه 29 !
حال که کلیت مسئله رو فهمیدیم بریم به حل این سوال.
برای حل این سوال 2 روش وجود داره ، که میتونید برای دیدن اون ها به ادامه مطلب مراجعه کنید.اما پیشنهاد میکنم قبلش یکم رو این مسئله فک کنید که یک روش بهینه ارائه بدید.

احتمالا اولین روش رو همه بهش رسیدید. اونم اینه که بیایم همه ی حالات رو حساب کنید که با یک پیاده سازی ساده و2تاحلقه میشه این کارو انجام داد و با اوردر ( O( n2حل  میشه .
پیاده سازی این روش به زبان ++C در ادامه هستش :

[php]
int maxSum(int arr[], int n)
{
// Initialize result
int res = INT_MIN;

// Consider rotation beginning with i
// for all possible values of i.
for (int i=0; i<n; i++)
{

// Initialize sum of current rotation
int curr_sum = 0;

// Compute sum of all values. We don’t
// acutally rotation the array, but compute
// sum by finding ndexes when arr[i] is
// first element
for (int j=0; j<n; j++)
{
int index = (i+j)%n;
curr_sum += j*arr[index];
}

// Update result if required
res = max(res, curr_sum);
}

return res;
}
[/php]

حال بریم سراغ روش اصلی با اوردر بهبنه تر .در این روش سعی میکنیم با استفاده ازچرخش های قبلی ، حاصل این چرخش رو بدست بیاریم ( یجورایی برنامه نویسی پویا Dynamic Programing  ) .
هر موقع که ما میایم و آرایه رو یک بار میچرخونیم و شیفت هم میدیم ، عملا این 2 اتفاق میفته :
1 – ضریب خونه i ام که قبلا 0 بوده میشه n-1 ؛ پس عملا این مقدار باید به حاصل مرحله قبل اضافه بشه .
2 – ضریب تمام خونه های دیگه هم یکی کم میشه ! پس باید از حاصل مرحله قبل این مقدار یعنی مجموع کل عناصر – عنصر i-1 که مجموع کل عناصر رو میتونیم همون اول و در متغیری به نام cum_sum ذخیره کرد.
حالا فرض کنید یک آرایه یه صورت زیر داشته باشیم :

{3, 2, 1}

اگر بیایم و با استفاده از روش دوم اینو حل کنیم داریم :
مقدار اولین چرخش میشه : 1*0+2*1+3*2 = 8
حالا یه بار شیفت میدیم آرایه میشه {2,3,1} و مقدار این چرخش میشه :
5 = 1*2 + (6-1) – 8
و برای شیفت بعدی که آرایه میشه {3,1,2}  به همین ترتیب. همینطور که میبینید میشه به راحتی با اوردر(O(n این مسئله رو حل کرد.در ادامه کد این روش به زبان ++C اومده :

[php]
int maxSum(int arr[], int n)
{
// Compute sum of all array elements
int cum_sum = 0;
for (int i=0; i<n; i++)
cum_sum += arr[i];

// Compute sum of i*arr[i] for initial
// configuration.
int curr_val = 0;
for (int i=0; i<n; i++)
curr_val += i*arr[i];

// Initialize result
int res = curr_val;

// Compute values for other iterations
for (int i=1; i<n; i++)
{
// Compute next value using previous value in
// O(1) time
int next_val = curr_val – (cum_sum – arr[i-1])
+ arr[i-1] * (n-1);

// Update current value
curr_val = next_val;

// Update result if required
res = max(res, next_val);
}

return res;
}
[/php]

دوستان میتونن اگه روش ، ایده و سوالی در مورد این مسئله داشتند در قسمت نظرات مطرح کنند .

 منبع : GeeksforGeeks

0

487 views

نویسنده: امیر محمد رستمی
درباره امیر محمد رستمی:


  1. Mr Mjob گفت:

    مطالب و منابعتان خیلی مفید بود.
    با تشکر

    0

طراحی سایت توسط تیم طراحی دانشجوی ایرانی

© تمامی حقوق مادی و معنوی این وب سایت متعلق به دانشجوی ایرانی می باشد.