Барган сайын көбөйүп бара жаткан максималдуу продукт


Кыйынчылык деңгээли жеңил
Көп суралган Accolite GE Саламаттыкты сактоо HackerRank IBM снэпчат Yahoo
согуштук тизме Динамикалык программалоо

Маселени билдирүү

"Өсүп келе жаткан ырааттуулуктун максималдуу көбөйтүүсү" көйгөйүндө сизге бүтүн сандар массиви берилгендиги айтылат. Эми сиз өсүп жаткан кийинки элементтердин санын көбөйтүп, жетише турган максималдуу өнүмдү табышыңыз керек. Белгилей кетчү нерсе, биз эң узак өсүп келе жаткан кийинки нерсени билишибиз керек эмес. Бизде андан кийинки кичирээк болушу мүмкүн, бирок ал максималдуу өнүмгө ээ болушу керек.

мисал

Барган сайын көбөйүп бара жаткан максималдуу продукт

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

Өсүп келе жаткан ырааттуулуктун максималдуу көбөйтүүсү 10, 1000ди түзөт. Эң узун өсүүчү ырааттуулук {1, 2, 3, 4}.

жакындоо

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

Ошентип, бул көйгөйдү чечүү үчүн. Маселени чечүү үчүн биз Brute Force Approach ыкмасын колдоно алабыз. Бул ыкма натыйжасыз, бирок билиш керек да. Ошентип, орой күч ыкмасында биз баардык кийинки нерселерди жаратабыз. Кийинки секвенцияларды жараткандан кийин биз текшерүүчү функцияны жаратабыз. Текшергич функциясы боюнча, кийинки орундуу экендигин текшеребиз. Текшергичтин функцияларынын жарамдуулугу, кийинчерээк өсүп бара жаткан секреция болушу керек дегенди билдирет. Андан кийин, биз өсүп келе жаткан кийинки изделген максималдуу продуктту жаңырта беребиз.

Эми маселени кантип натыйжалуу чечебиз? Маселени натыйжалуу чечүү үчүн, биз Динамикалык программалоону колдонобуз. Маселенин өтүшү ЛИС көйгөйү менен бирдей. Биздин 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 таблицасын түзөбүз. Ошентип космос татаалдыгы сызыктуу.