Айрым айырмачылыктары бар жуптардын максималдуу суммасы


Кыйынчылык деңгээли жеңил
Көп суралган Accolite Coursera Delhivery Fourkites Snapdeal
согуштук тизме Динамикалык программалоо

"Айрым айырмачылыгы бар жуптардын максималдуу суммасы" көйгөйүндө сизге массив берилген бүтүн жана бүтүндөй К. Андан кийин көзкарандысыз түгөйлөрдүн максималдуу суммасын билүү сунушталат. Эгер эки бүтүн сандын абсолюттук айырмасы К ден кем болсо, аларды жупташтыра алабыз, ошондуктан биз 2 х сандардан турган мындай жуптардын максималдуу суммасын табышыбыз керек.

мисал

Айрым айырмачылыктары бар жуптардын максималдуу суммасы

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

түшүндүрүү

Биз 42, 43 жана 5, 6ды тандайбыз. Бизде 4, 5 жана 6нын варианттары бар болчу. Ошентип, натыйжада алардын ичинен максималдуу мааниге ээ болобуз = 96.

жакындоо

Маселе, эгерде кээ бир элементтерин жупташтырсак, анда мүмкүн болгон максималдуу сумманы табууну сурайт согуштук тизме. Элементтердин абсолюттук айырмасы К ден ашпашы керек деген шартта элементтерди жупташтыра алабыз. Маселени чечүүдөн мурун биз түрү массив. Ошентип, биз издөө мейкиндигибизди кесебиз. Бизде сорттолбогон массив бар болчу. Андан кийин бир элементти жупташтыруу үчүн бардык элементтерди басып өтүшүбүз керек. Бирок иргелип бүткөндөн кийин, эң чоң элемент - бул ага чейинки элемент гана экендигин билебиз. Ошентип, шарттын канааттандырылгандыгын текшеребиз.

Эгер шарт аткарылса, анда мурунку жана учурдагы элементти жуптап, маселенин жыйынтыгын акыркы экинчи элементке чейин кошобуз (учурдагы элементтен). Бирок шарт канааттандырылбаса. Жупташтырууну калтырабыз жана натыйжа мурунку элементке чейинкилер менен бирдей. Расмий түрдө, натыйжа [i] = натыйжа [i-2] + киргизүү [i] + киргизүү [i-2], эгерде жупташуу аткарылса [i] = натыйжа [i-1]. Бул жерде бул жыйынтык массиви биздики DP массив, анткени биз кичинекей чакан көйгөйлөрдүн натыйжаларын сактап жатабыз. Биз ушул чакан чакан көйгөйлөрдүн натыйжаларын бириктирип, баштапкы көйгөйдүн натыйжасын табабыз, ылдыйдан өйдө DP сыяктуу эле.

коду

Айрым айырмачылыктары бар жуптардын максималдуу суммасын табуу үчүн C ++ коду

#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

Айрым айырмачылыктары бар жуптардын максималдуу суммасын табуу үчүн Java коду

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

Комплекстик анализ

Убакыт татаалдыгы 

O (NlogN), анткени биз башында массивди иреттеп алдык. Жана сорттоо жана башка сорттоо алгоритмдери O (NlogN) массивин иреттей алат. Эгерде бизге иреттелген киргизүү сунушталса, анда O (N) убакытта маселени чечип алмакпыз.

Космостун татаалдыгы

O (N), бул орун массивди иреттөө үчүн талап кылынат. Биз DP массивин түзбөсөк дагы жана DP үстөлү үчүн ошол эле киргизүү массивин колдонмокпуз. Бул чечим дагы эле мейкиндиктин татаалдыгына ээ, анткени бул орун сорттоо үчүн талап кылынат.