وڌ ۾ وڌ جوڑوں جو وڌ ۾ وڌ فرق


تڪليف جي سطح آسان
بار بار پڇڻ ۾ قبول ڪريو Coursera دهلي چار چار اسپيڊل
ڪيريو متحرڪ پروگرامنگ

مسئلو ”مخصوص فرق سان جوڙو جو وڌيڪ مقدار“ ٻڌائي ٿو ته توهان کي هڪ صف جو درجو ڏنو ويو آهي جيتريون ۽ هڪ انٽيگر K. ان کان پوءِ اسان کي چيو وڃي ٿو ته آزاد جوڑوں جو وڌ کان وڌ مقدار معلوم ڪيو وڃي. اسان ٻه عدد گڏيل ڪري سگهون ٿا جيڪڏهن انهن کي K. کان گهٽ جو مڪمل فرق آهي ، تنهن ڪري اسان کي ايڪس x جي وڌ کان وڌ رقم ڳولڻ جي ضرورت آهي جيڪا 2x عدد آهي.

مثال

وڌ ۾ وڌ جوڑوں جو وڌ ۾ وڌ فرق

42, 43, 4, 5, 6, 12
96

وضاحت

اسان 42 ، 43 ، ۽ 5 ، 6. ڇنڇرون اختيار ڪيون ، اسان وٽ 4 ، 5 ، ۽ 6. وٽ اختيار آهن ، تنهن ڪري ، اسان نتيجو ٺاهيو ته انهن مان وڌ ۾ وڌ قدر = 96.

چرچو

مسئلو اسان کان پڇي ٿو وڌ کان وڌ رقم ڳولڻ لاءِ جيڪو حاصل ڪري سگھجي ٿو جيڪڏهن اسان ڪجھ عناصر جا حصا ڏيون صف. اسان عناصر کي لاڳو ڪيل شرط تحت جوڙي سگهون ٿا ته عنصرن کي K. کان گهٽ جو مڪمل فرق هجڻ گهرجي ، مسئلي کي حل ڪرڻ کان پهريان ، اسان ترتيب ڏيو صف. انهي طريقي سان اسين پنهنجي ڳولا جي جڳهه کي ڪٺو ڪري رهيا آهيون. غور ڪريو اسان وٽ ھڪڙي اڻ ترتيب وار صف ھئي. پوءِ اسان کي هڪ عنصر جوڙي ٺاهڻ جي لاءِ سڀني عنصرن کي گهورڻو پوندو. پر ترتيب ڏيڻ کان پوءِ اسان thatاڻون ٿا ته سڀ کان وڏو عنصر صرف اهو عنصر آهي جيڪو ان کان پهرين آهي. تنهن ڪري اسان چڪاسون ته اها شرط مطمئن آهي.

جيڪڏهن حالت مطمئن آهي ، اسين پوئين ۽ هاڻوڪو عنصر جوڙي ۽ ڪ secondي ٿو آخري مسئلي تائين مسئلو کي آخري ٻئي عنصر (موجوده عنصر کان). پر جيڪڏهن شرط مطمئن نه ٿي. اسان جوڙي ڇڏي ڏيو ۽ نتيجو ساڳيو ساڳيو آهي جيڪو گذريل عنصر تائين. وڌيڪ رسمي طور ، نتيجو [i] = نتيجو [i-2] + انپٽ [i] + انپٽ [i-2] ، جيڪڏهن ٻلڻ ٻئي ڪم ڪيو وڃي ته نتيجو [i] = نتيجو [i-1]. هتي هي نتيجو واري ترتيب اسان جي آهي DP ڇاڪاڻ ته اسان نن subن ذيلي منصوبن جو نتيجو محفوظ ڪري رهيا آهيون. اسان انهن نن subن ذيلي مسئلن جو نتيجو گڏ ڪريون اصل مسئلي جو نتيجو ڳولڻ لاءِ جيئن اسين هيٺيان ڊي پي ۾ ڪريون.

ڪوڊ

سي ++ ڪوڊ مخصوص فرق سان جوڑوں جي وڌ ۾ وڌ مقدار ڳولڻ لاءِ

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

جاوا ڪوڊ مخصوص فرق سان جوڑوں جي وڌ ۾ وڌ مقدار ڳولڻ لاءِ

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

پيچيدگي تجزيي

وقت جي پيچيدگي 

اي (بلاگ اين) ، اهو ئي سبب آهي ڇاڪاڻ ته اسان شروعاتي طور تي صف ترتيب ڏني هئي. ۽ ضم ڪريو ترتيب ۽ ٻين ترتيب وار الگورتھم ترتيب ڏئي سگهو ٿا صف ۾ آر (NlogN). جيڪڏهن اسان کي ترتيب وارين ان پٽ فراهم ڪئي وڃي ها ، اسان O (N) وقت ۾ مسئلو حل ڪري سگهون ها.

خلائي پيچيدگي

اي (اين) ، ھن جڳھ کي گھربل ترتيب ڏيڻ لاءِ گھربل آھي. جيتوڻيڪ جيڪڏهن اسان ڊي پي جي صف نه ٺاهي ها ۽ ڊي پي ٽيبل لاءِ ساڳئي انٽري صف استعمال ڪريون ها. اھو حل اڃا تائين ساڳي جڳھ جي پيچيدگي آھي ڇو ته ھن جڳھ کي ترتيب ڏيڻ جي ضرورت آھي.