ផលបូកកើនឡើងជាអតិបរមា

កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម Atlassian ទីភ្នាក់ងារ Bloomberg ByteDance Citrix លេខកូដ គូប៉ាង របស់ eBay Facebook ក្រុមហ៊ុន google ក្រុមហ៊ុន IBM ក្រុមហ៊ុន Microsoft ណាហ្គារ៉ូ ក្រុមហ៊ុន Oracle Uber ក្រុមហ៊ុន Yahoo
អារេ ការស្វែងរកគោលពីរ ការសរសេរកម្មវិធីឌីណាមិកចំនួនមើល 449

សំណួរសំភាសន៍រចនាប្រព័ន្ធ អាចជាការបើកចំហរ ដូច្នេះវាពិបាកពេកក្នុងការដឹងពីវិធីត្រឹមត្រូវក្នុងការរៀបចំ។ ឥឡូវនេះខ្ញុំអាចបំបែកការរចនានៃ Amazon, Microsoft និង Adobe បន្ទាប់ពីទិញ សៀវភៅ​នេះ. ពិនិត្យឡើងវិញប្រចាំថ្ងៃ សំណួររចនា ហើយខ្ញុំសន្យាថាអ្នកអាចបំបែកការរចនាជុំ។

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហា“ ផលបូកនៃផលបូកអតិបរិមា” យើងបានផ្តល់អោយ អារេ។ រកផលបូកនៃការបន្តអតិបរិមានៃអារេដែលបានផ្តល់នោះគឺជាចំនួនគត់ក្នុងបនា្ទាប់គឺស្ថិតនៅក្នុងលំដាប់តម្រៀប

បនា្ទាប់គឺជាផ្នែកមួយនៃអារេដែលជាលំដាប់ដែលកើតចេញពីលំដាប់មួយទៀតដោយលុបធាតុមួយចំនួនដោយមិនផ្លាស់ប្តូរលំដាប់។ នេះអាចត្រូវបានពន្យល់នៅក្នុងឧទាហរណ៍ខាងក្រោម។

ឧទាហរណ៍

4
18 5 17 23
45

ការពន្យល់: ក្នុងឧទាហរណ៍ខាងលើ ៤៥ គឺជាផលបូកអតិបរមា។ ក្នុងឧទាហរណ៍ខាងលើមានការកើនឡើងជាបន្តបន្ទាប់ពីរគឺ {១៨, ១៧} និង {៥, ១៧, ២៣} ។ ប៉ុន្តែការបន្តលើកទីពីរមានផលបូកអតិបរមា។

វិធីសាស្រ្ត

បានផ្តល់អារេនៃចំនួនវិជ្ជមាន។ យើងត្រូវគណនាផលបូកនៃផលបូកអតិបរិមានៃអារេដែលជាបន្តបន្ទាប់គឺស្ថិតនៅក្នុងការកើនឡើង។ 

ឧទាហរណ៍ -  [2,5,8,3,4,6]

បន្ទាប់មកការកើនឡើងជាបន្តបន្ទាប់គឺ - 

[២,៥,៨], ផលបូក = ១៥

[២,៥,៨], ផលបូក = ១៥

[៥.៨], ផលបូក = ១៣

[2,3,4,6], ផលបូក = 15

[2,5,6], ផលបូក = 13 ផលបូកអតិបរមាដែលយើងទទួលបានគឺ ១៥ ។

បញ្ហាអាចត្រូវបានបំបែកទៅជាឧបសម្ព័ន្ធសាមញ្ញដែលមានន័យថាវាមាន ហេដ្ឋារចនាសម្ព័ន្ធល្អប្រសើរបំផុត។ ហើយបញ្ហាក៏មានផងដែរ ឧបសម្ព័ន្ធរងត្រួតគ្នា ប្រសិនបើយើងគូរមែកឈើហៅខ្លួនឯង។ ដោយសារបញ្ហានេះមានរចនាសម្ព័ន្ធរងល្អប្រសើរនិងឧបសម្ព័ន្ធរងត្រួតគ្នាបញ្ហាអាចត្រូវបានដោះស្រាយដោយប្រើ ការសរសេរកម្មវិធីថាមវន្ត. តាង a [0,1, …… n-1] ជាអារេនិង dp [i] = ផលបូកការកើនឡើងជាអតិបរមាបន្តដោយបញ្ចប់នៅសន្ទស្សន៍ i ដូចជា a [i] គឺជាធាតុចុងក្រោយ។

បន្ទាប់មក dp [i] អាចត្រូវបានសរសេរជា 

dp [i] = a [i] + អតិបរមា (L [j]) ដែលលេខ ០

អ្នកឆ្លើយនឹងមានចំនួនអតិបរមា (dp [i]) ដែលលេខ ០

វិធីសាស្រ្ត

  1. យើងនឹងបង្កើតអារេថ្មី dp ដែល dp [i] = a [i], ដែល 0
  2. យើងនឹងដំណើរការរង្វិលជុំខាងក្រៅពី ០ <i <n ។
  3. សម្រាប់ i នីមួយៗដែលផ្ទុកនូវផលបូកអតិបរិមាកើនឡើងជាបន្តបន្ទាប់នៃ [0, i-1] ដែលបញ្ចប់ដោយអាយ។ ការកើនឡើងជាបន្តបន្ទាប់ដោយការបូកអតិបរមាដែលបញ្ចប់ដោយ [ជ] ដែល a [j] តិចជាងធាតុបច្ចុប្បន្ន a [i]
  4. រកអតិបរិមាក្នុងអារេឌី។

ការអនុវត្តន៍

កម្មវិធី 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;
}

កម្មវិធីចាវ៉ាសម្រាប់ផលបូកការកើនឡើងជាអតិបរមា

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 គឺជាទំហំនៃអារេដែលបានផ្តល់។ នៅទីនេះយើងដំណើរការពីរជួរសម្រាប់រង្វិលជុំដែលនាំយើងឱ្យស្មុគស្មាញពេលវេលាស្មុគស្មាញ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ពីព្រោះយើងប្រើអារេ 1-D ។ នៅទីនេះយើងរក្សាទុកតម្លៃនៅក្នុងអារេឌីអ័រលីនេអ៊ែរ។

បទសម្ភាសន៍រចនាប្រព័ន្ធបំបែក
Translate »