Максимални производ све веће подсеквенце  


Ниво тешкоће Лако
Често питани у Аццолите ГЕ Хеалтхцаре ХацкерРанк ИБМ- Снапцхат иахоо
Ред Динамичко програмирање

Изјава о проблему  

Проблем „Максимални производ растуће подредности“ наводи да вам је дат низ целих бројева. Сада морате да сазнате максимум производа који можете постићи тако да множите елементе све веће подсекције. Треба напоменути да не би требало да сазнамо најдуже растућу подсеквенцу. Можда имамо мању подсеквенцу, али она треба да има максималан производ.

Пример  

Максимални производ све веће подсеквенцеПин

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

Максимални производ растуће подсекције је 10, 1000. Иако је најдужа растућа подсеквенца {1, 2, 3, 4}.

Приступ  

Проблем подсећа на Најдужа све већа последица Проблем. Мала измена у вези са тим проблемом је та што уместо проналажења најдуже растуће подсеквенце. Морамо пронаћи максималан производ све веће подсеквенце.

Дакле, за решавање овог проблема. Приступ грубе силе можемо користити и за решавање проблема. Иако је овај метод неефикасан, али би га требало знати. Дакле, у приступу грубе силе, прво ћемо генерисати све следове. Након генерисања подсеквенци, креирамо функцију провере. У функцији провере проверавамо да ли је подредност важећа. Ваљаност функције провере значи да подредност треба да буде све већа подсекција. Након тога настављамо да ажурирамо максималан производ пронађен из све веће подсекције.

Види такође
Најдужи уобичајени префикс помоћу сортирања

Сада се поставља питање како ефикасно решити проблем? Да бисмо ефикасно решили проблем, користимо динамичко програмирање. Прелаз у проблему је исти као и проблем ЛИС-а. Наш ДП низ чува максимум производа који се може постићи ако узмемо у обзир све елементе до тренутног елемента. И постоји још један услов да подредност садржи тренутни елемент. Затим за израчунавање ДП низа покрећемо угнежђену петљу у обрнутом смеру од тренутног елемента до почетног елемента. Ако пронађемо елемент који је мањи од тренутног елемента, ажурирамо одговор ако је множење тренутног елемента елементом при том индексу у низу ДП веће од тренутно ускладиштене вредности.

код  

Ц ++ код за проналажење максималног производа растуће подсекције

#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

Јава код за проналажење максималног производа све веће подсеквенце

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

Анализа сложености  

Сложеност времена

О (Н ^ 2) јер користимо две угнежђене петље. Једна која прелази све елементе, а друга унутрашња петља прелази све елементе до тренутног елемента.

Види такође
Сингле Нумбер

Сложеност простора

О (Н) јер креирамо једнодимензионалну ДП табелу. Стога је сложеност простора линеарна.