Маҳсулоти максималии пайдарпайии афзоянда  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Акколити GE Тандурустӣ HackerRank IBM Snapchat Yahoo
тартиботи ҳарбӣ Барномарезии динамикӣ

Изҳороти мушкилот  

Масъалаи "Ҳосили максималии пайдоиши афзоиш" изҳор мекунад, ки ба шумо массиви бутун дода мешавад. Акнун ба шумо лозим аст, ки маҳсули ҳадди аксарро ба даст оред, то унсурҳои пайдоиши афзояндаро афзун кунед. Чизе, ки бояд қайд кард, ин аст, ки мо набояд дарозтарин пайдоиши афзояндаро пайдо кунем. Мо метавонем пайдарпайии хурдтар дошта бошем, аммо он бояд ҳадди аксар маҳсулот дошта бошад.

мисол  

Маҳсулоти максималии пайдарпайии афзоянда

10, 1, 1000, 2, 3, 4
10000

Ҳосили максималии пайдоиши афзоиш 10, 1000 мебошад. Гарчанде ки пайдоиши дарозтарин афзоиш {1, 2, 3, 4} бошад.

усул  

Масъала ба Дарозии афзояндаи дарозтарин Мушкилот. Тағироти ночиз дар ин масъала ин аст, ки ба ҷои дарёфт кардани пайдоиши дарозтарин. Мо бояд ҳадди аксар ҳосили афзояндаи пайдарпайро пайдо кунем.

Пас, барои ҳалли ин мушкилот. Барои ҳалли мушкилот мо инчунин метавонем аз усули Brute Force Approach истифода барем. Ҳарчанд ин усул бесамар аст, аммо бояд донист. Ҳамин тавр, дар равиши қувваи бераҳмона, мо пеш аз ҳама ҳамаи пасояндҳоро тавлид хоҳем кард. Пас аз тавлид кардани пайдарпайҳо, мо функсияи checker месозем. Дар функсияи checker, мо тафтиш мекунем, ки оё баъд аз он дуруст аст. Эътибори функсияи Checker маънои онро дорад, ки пайдарпа бояд пайдарҳамии афзоянда бошад. Пас аз он, мо навсозии ҳадди аксар маҳсулоти аз паси афзоянда пайдошударо идома медиҳем.

ҳамчунин нигаред
Дарозтарин префикси маъмул бо истифодаи Sorting

Ҳоло саволе ба миён меояд, ки чӣ гуна мо мушкилро самаранок ҳал мекунем? Барои ҳалли самараноки масъала, мо барномасозии динамикиро истифода мебарем. Гузариш дар мушкилот ҳамон тавре ки мушкилоти ЛИС мебошад. Массиви DP-и мо ҳадди аксар маҳсулотеро нигоҳ медорад, ки ба даст овардан мумкин аст, агар мо ҳамаи унсурҳоро то унсури ҷорӣ баррасӣ кунем. Ва боз як шарти дигаре мавҷуд аст, ки зерсистема бояд унсури ҷориро дар бар гирад. Пас барои ҳисоб кардани массиви DP мо як ҳалқаи лонаеро ба самти ақиб аз унсури ҷорӣ ба унсури ибтидоӣ мегузаронем. Агар мо унсури хурдтар аз унсури ҳозираро ёбем, пас ҷавоби худро нав месозем, агар зарб кардани унсури ҳозираро ба унсури ин нишондиҳанда дар массиви DP аз аҳамияти ҳозираи ҳифзшуда зиёдтар кунад.

рамз  

Коди C ++ барои дарёфт кардани ҳосили максималии пайдоиши афзоянда

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


int maxProductOfIncreasingSubsequence(vector<int> &input){
  vector<int> dp(n);
  dp[0] = input[0];
  int ans = input[0];
  for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
      if(input[j] < input[i])
        dp[i] = max(dp[i], dp[j]*input[i]);
    }
    ans = max(ans, dp[i]);
  }
  return ans;
}

int main(){
  int n;cin>>n;
  vector<int> input(n);
  for(int i=0;i<n;i++)
    cin>>input[i];

  cout<<maxProductOfIncreasingSubsequence(input);
}
6
10 1 1000 2 3 4
10000

Рамзи Java барои дарёфт кардани маҳсули максималии пайдоиши афзоянда

import java.util.*;

class Main{
    static int maxProductOfIncreasingSubsequence(ArrayList<Integer> input){
    ArrayList<Integer> dp = new ArrayList<Integer>();
    dp.add(input.get(0));
    int ans = input.get(0);
    int n = input.size();
    for(int i=1;i<n;i++){
      dp.add(input.get(i));
      for(int j=0;j<i;j++){
        if(input.get(j) < input.get(i))
          dp.set(i, Math.max(dp.get(i), dp.get(j)*input.get(i)));
      }
      ans = Math.max(ans, dp.get(i));
    }
    return ans;
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> input = new ArrayList<>();
    for(int i=0;i<n;i++){
      int in = sc.nextInt();
      input.add(in);
    }

    int answer = maxProductOfIncreasingSubsequence(input);
    System.out.print(answer);
  }
}
6
10 1 1000 2 3 4
10000

Таҳлили мураккабӣ  

Мураккабии вақт

O (N ^ 2), зеро мо аз ду ҳалқаи лона истифода мекунем. Яке, ки аз болои тамоми элементҳо мегузарад ва дигар ҳалқаи ботинӣ аз болои тамоми унсурҳо то элементҳои ҷорӣ мегузарад.

ҳамчунин нигаред
Рақами ягона

Мураккабии фазо

O (N), зеро мо ҷадвали DP-и якандозаро месозем. Ҳамин тариқ, мураккабии фазо хаттӣ аст.