Үр дагаврыг нэмэгдүүлэх хамгийн дээд хэмжээ

Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Apple-ийн Atlassian Bloomberg БайтДанс Citrix CodeNation Купанг Ebay Facebook-ийн Google-ийн IBM Microsoft- Нагарро Oracle-ийн Uber Yahoo
Array Хоёртын хайлт Динамик програмчлалҮзэлт 436

Системийн дизайны ярилцлагын асуултууд маш нээлттэй байж болох тул зөв бэлтгэх арга замыг мэдэхэд хэтэрхий хэцүү байдаг. Одоо би худалдаж авсны дараа Amazon, Microsoft, Adobe-ийн дизайныг эвдэх боломжтой болсон энэ ном. Өдөр бүр нэг засвар хийх дизайны асуулт Мөн би та дизайны дугуйг эвдэж чадна гэж амлаж байна.

Асуудлын мэдэгдэл

“Үр дагаврыг нэмэгдүүлэх хамгийн дээд нийлбэр” асуудалд бид массив. Өгөгдсөн массивын хамгийн их дарааллын нийлбэрийг ол, өөрөөр хэлбэл дарааллын бүхэл тоо эрэмбэлэгдсэн байна.

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

Жишээ нь

4
18 5 17 23
45

Тайлбар: Дээрх жишээнд 45 нь хамгийн их нийлбэр юм. Дээрх жишээнд өсөн нэмэгдэж буй хоёр дараалал байна, өөрөөр хэлбэл, {18, 17} ба {5, 17, 23}. Гэхдээ хоёр дахь дараалал нь хамгийн их нийлбэртэй байна.

арга барил

Массив эерэг тоонууд өгөгдсөн. Бид массивын хамгийн их нийлбэр дарааллын нийлбэрийг дараалал нь нэмэгдэх_зэрэгт байхаар тооцох ёстой. 

Жишээ-  [2,5,8,3,4,6]

Дараа нь нэмэгдэж буй зарим дараалал нь - 

[2,5,8], нийлбэр = 15

[2,8], нийлбэр = 10

[5,8], нийлбэр = 13

[2,3,4,6], нийлбэр = 15

[2,5,6], нийлбэр = 13 гэх мэт Бидний авах хамгийн дээд нийлбэр нь 15 байна.

Асуудлыг энгийн дэд асуудлуудад хувааж болох бөгөөд энэ нь түүнд байгаа гэсэн үг юм оновчтой дэд бүтэц. Асуудал бас бий давхардсан дэд асуудлууд Хэрэв бид түүний рекурсын модыг зурвал. Асуудал нь оновчтой дэд бүтэцтэй, давхардсан дэд асуудлуудтай тул асуудлыг ашиглан шийдэж болно динамик програмчлал. A [0,1, …… n-1] нь массив байх ба dp [i] = i индексээр төгссөн хамгийн их нийлбэр нэмэгдэх дараалал байг.

Дараа нь dp [i] гэж бичиж болно, 

dp [i] = a [i] + max (L [j]) хаана 0

Ans нь max (dp [i]) байх ба 0 болно

арга барил

  1. Бид dp шинэ массив үүсгэх болно, dp [i] = a [i], хаана 0
  2. Бид гаднах гогцоог 0 <i <n-ээс ажиллуулна.
  3. I-ээр төгссөн a [0, i-1] -н дарааллыг нэмэгдүүлэх хамгийн их нийлбэрийг хадгалдаг i бүрийн хувьд. FI нь одоогийн j [a] элементээс бага байх тохиолдолд [j] -ээр төгсөх хамгийн дээд нийлбэрээр дарааллыг нэмэгдүүлнэ.
  4. Dp массиваас хамгийн дээд хэмжээг ол.

Хэрэгжүүлэх

Хамгийн их нийлбэр үржлийг нэмэгдүүлэх C ++ хөтөлбөр

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

int max_sum_inc_sub(vector<int> a,int n){
  vector<int> dp(a);
  int ans = 0;
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
        dp[i] = dp[j]+a[i];
      }
    }
    ans = max(ans,dp[i]);
  }
  return ans;
}
int main() {
  int n;
  cin>>n;
  vector<int> a;
  for(int i=0;i<n;i++){
    int x;cin>>x;
    a.push_back(x);
  }
  int max_sum = max_sum_inc_sub(a,n);
  cout<<max_sum<<endl;
  return 0;
}

Хамгийн их нийлбэр дүнг нэмэгдүүлэх Java хөтөлбөр

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int ans = max_sum_inc_sub(arr,n);
        System.out.println(ans);
  }
  
  public static int max_sum_inc_sub(int[] a,int n){
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
        	dp[i]=a[i];
        }
        int ans = 0;
    for(int i=1;i<n;i++){
      for(int j=0;j<i;j++){
        if(a[i]>a[j] && dp[i]<dp[j]+a[i]){
          dp[i] = dp[j]+a[i];
        }
      }
      ans = Math.max(ans,dp[i]);
    }
    return ans;
    }

}
6
2 5 8 3 4 6
15

Үр дагаврыг нэмэгдүүлэх хамгийн дээд нийлбэр дүн шинжилгээ

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

O (n * n) хаана n гэдэг нь өгөгдсөн массивын хэмжээ юм. Энд бид хоёр гогцоонд үүрлэсэн бөгөөд энэ нь квадрат цагийн нарийн төвөгтэй байдалд хүргэдэг.

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

O (N) Учир нь бид 1 хэмжээст массив ашигладаг. Энд бид утгыг шугаман dp массивт хадгалдаг.

Crack системийн дизайны ярилцлага
Translate »