Хамгийн их дарааллын нийлбэр нь гурвуулаа дараалалгүй байхаар байна


Хэцүү байдлын түвшин Дунд
Байнга асуудаг 24 * 7 инновацийн лаборатори Accenture Амазоны Дели PayPal PayU
Array Динамик програмчлал

"Гурван дараалсан дараалалгүй байхаар хамгийн их дарааллын нийлбэр" гэсэн асуудалд танд массив of бүхэл тоо. Одоо та гурван элементийг дараалан авч үзэж чадахгүй тул хамгийн их нийлбэр бүхий дарааллыг олох хэрэгтэй. Дахин санах нь дарааллыг хэвээр хадгалж анхны оролтын массиваас зарим элементүүдийг хасахад үлдэх массиваас өөр зүйл биш юм.

Жишээ нь

Хамгийн их дарааллын нийлбэр нь гурвуулаа дараалалгүй байхаар байна

a[] = {2, 5, 10}
50

Тайлбар

Энэ нь 5 ба 10-ыг сонгоход хялбар сонголт байв. Учир нь өөр аргаар илүү их дүн гарахгүй.

a[] = {5, 10, 5, 10, 15}
40

Тайлбар

Бид массивын дунд байгаа 5-г сонгодоггүй. Учир нь энэ нь тухайн асуултанд тавигдсан нөхцлийг хангаагүй дэд дарааллыг бий болгоно.

арга барил

Асуудал нь дараалсан гурван элемент сонгогдохгүй байхын тулд хамгийн их нийлбэр бүхий дарааллыг олохыг биднээс хүссэн. Тиймээс гэнэн хандлага нь дараахь үеийг бий болгож чаддаг. Өмнөх асуултуудын заримыг бид хийсэн шиг. Ихэнхдээ гэнэн хандлага бол дэд дарааллыг бий болгож дараа нь уг асуултанд тавигдсан нөхцлийг хангаж байгаа эсэхийг шалгах явдал юм. Гэхдээ энэ хандлага нь цаг хугацаа их шаарддаг тул практикт ашиглах боломжгүй юм. Учир нь дунд зэргийн хэмжээтэй оролтод ашиглах аргыг ашиглах нь цаг хугацааны хязгаараас хэтрэх болно. Асуудлыг шийдэхийн тулд бид өөр аргыг ашиглах хэрэгтэй.

Бид ашиглах болно Динамик програмчлал асуудлыг шийдэхийн тулд үүнээс өмнө зарим нэг даалгаврыг гүйцэтгэх хэрэгтэй. Энэхүү анхан шатны даалгавар нь анхны асуудлыг жижиг дэд асуудал болгон багасгах зорилгоор хийгдсэн болно. Учир нь динамик програмчлалд бид асуудлыг жижиг дэд асуудлууд болгон багасгадаг. Тиймээс одоо байгаа элементийг алгасаж үзэхэд бидний асуудал өмнөх элемент хүртэл асуудлыг шийдвэрлэх хүртэл багасна. Бид одоогийн элементийг сонгож авдаг. Дараа нь бид өмнөх элементийн хувьд хоёр сонголт байна. Эсвэл бид өмнөх элементийг сонгодог, хэрэв тэгвэл бид өмнөх элементээс өмнөх элементийг сонгож чадахгүй. Гэхдээ хэрэв үгүй ​​бол асуудал өмнөх элемент рүү шилжих хүртэл асуудал шийдэгдэх болно. Кодыг ашиглан ойлгоход хялбар байх болно.

код

Хамгийн их дарааллын нийлбэрийг олохын тулд C ++ код нь дараалсан гурвуулаа байх ёсгүй

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

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
    int dp[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = max({a[0] + a[1], a[2]+a[0], a[2]+a[1]});
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = max({a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i], dp[i-1]});
    cout<<dp[n-1];
}
16

Хамгийн их дарааллын нийлбэрийг олохын тулд Java код дараалан гурвуулаа байх ёсгүй

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int a[] = {1, 2, 3, 4, 5, 6};
    int n = a.length;
    int dp[] = new int[n];

    // base case
    if(n>=0)dp[0] = a[0];
    if(n>0)dp[1] = a[0] + a[1];
    if(n>1)dp[2] = Math.max(Math.max(a[0] + a[1], a[2]+a[0]), a[2]+a[1]);
    // if you choose a[i], then choose a[i-1] that is dp[i] = a[i]+a[i-1]+dp[i-3]
    // if you choose a[i], then you do not choose a[i-1] dp[i] = dp[i-2] + a[i]
    // if you do not choose a[i], dp[i] = dp[i-1]
    for (int i = 3; i < n; i++)
        dp[i] = Math.max(Math.max(a[i]+a[i-1]+dp[i-3], dp[i-2]+a[i]), dp[i-1]);

    System.out.println(dp[n-1]);
  }
}
16

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), Учир нь бид массивыг дайран өнгөрч, АН-ынхаа массивыг үргэлжлүүлэн дүүргэж байсан. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь шугаман юм.

Сансрын нарийн төвөгтэй байдал

O (N), Учир нь бид утгыг хадгалахын тулд нэг хэмжээст DP массив хийх ёстой байсан. Сансрын нарийн төвөгтэй байдал нь мөн шугаман юм.