ផលបូកអតិបរមានៃគូជាមួយនឹងភាពខុសគ្នាជាក់លាក់


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ គួរឱ្យគោរព Coursera ដេលីវ៉ាយ Fourkites Snapdeal
អារេ ការសរសេរកម្មវិធីឌីណាមិក

បញ្ហា“ ផលបូកអតិបរិមានៃគូនិងភាពខុសគ្នាជាក់លាក់” ចែងថាអ្នកត្រូវបានផ្តល់ជូន ចំនួនគត់ និងលេខគត់ឃ។ បន្ទាប់មកយើងត្រូវបានស្នើសុំឱ្យរកចំនួនសរុបអតិបរមានៃគូឯករាជ្យ។ យើងអាចផ្គូផ្គងចំនួនគត់ពីរប្រសិនបើពួកគេមានភាពខុសគ្នាដាច់ខាតតិចជាងឃ។ ដូច្នេះយើងត្រូវរកផលបូកអតិបរិមានៃគូ x ដែលជាចំនួន ២ គុណ។

ឧទាហរណ៍

ផលបូកអតិបរមានៃគូជាមួយនឹងភាពខុសគ្នាជាក់លាក់

42, 43, 4, 5, 6, 12
96

ការពន្យល់

យើងជ្រើសរើសយកលេខ ៤២, ៤៣ និង ៥, ៦ យើងមានជំរើសក្នុងចំនោម ៤, ៥ និង ៦ ។ ដូច្នេះយើងយកតំលៃអតិបរិមាក្នុងចំណោមពួកគេបង្កើតលទ្ធផល = ៩៦ ។

វិធីសាស្រ្ត

បញ្ហាស្នើឱ្យយើងរកផលបូកអតិបរមាដែលអាចទទួលបានប្រសិនបើយើងផ្គូរផ្គងធាតុមួយចំនួននៃឯកសារ អារេ។ យើងអាចផ្គុំធាតុក្នុងល័ក្ខខ័ណ្ឌដែលបានកំណត់ថាធាតុគួរមានភាពខុសគ្នាដាច់ខាតតិចជាងឃេមុនពេលដោះស្រាយបញ្ហាយើង ជោគវាសនា អារេ។ វិធីនេះយើងកំពុងកាត់ចេញចន្លោះស្វែងរករបស់យើង។ ពិចារណាថាយើងមានអារេដែលមិនបានរៀបជាស្រេច។ បន្ទាប់មកយើងត្រូវឆ្លងកាត់ធាតុទាំងអស់សម្រាប់ផ្គូរផ្គងធាតុមួយ។ ប៉ុន្តែបន្ទាប់ពីការតម្រៀបយើងដឹងថាធាតុធំបំផុតគឺគ្រាន់តែជាធាតុដែលមានពីមុន។ ដូច្នេះយើងពិនិត្យមើលថាតើលក្ខខណ្ឌនេះពេញចិត្តឬអត់។

ប្រសិនបើលក្ខខណ្ឌពេញចិត្តយើងភ្ជាប់ធាតុមុននិងបច្ចុប្បន្នហើយបន្ថែមលទ្ធផលសម្រាប់បញ្ហារហូតដល់ធាតុទីពីរចុងក្រោយ (ពីធាតុបច្ចុប្បន្ន) ។ ប៉ុន្តែប្រសិនបើលក្ខខណ្ឌមិនពេញចិត្ត។ យើងចាកចេញពីការផ្គូរផ្គងហើយលទ្ធផលគឺដូចគ្នាទៅនឹងធាតុមុនដែរ។ ជាផ្លូវការបន្ថែមទៀតលទ្ធផល [i] = លទ្ធផល [i-2] + បញ្ចូល [i] + បញ្ចូល [i-2] ប្រសិនបើការផ្គូរផ្គងត្រូវបានធ្វើរួចលទ្ធផលផ្សេងទៀត [i] = លទ្ធផល [i-1] ។ នៅទីនេះអារេលទ្ធផលនេះគឺជារបស់យើង DP អារេពីព្រោះយើងកំពុងរក្សាទុកលទ្ធផលនៃអនុរងតូចៗ។ យើងរួមបញ្ចូលគ្នានូវលទ្ធផលនៃគំរូរងតូចៗទាំងនេះដើម្បីរកលទ្ធផលនៃបញ្ហាដើមដូចដែលយើងបានធ្វើនៅក្នុងឌីភីក្រោម។

លេខកូដ

លេខកូដ C ++ ដើម្បីរកផលបូកអតិបរមានៃគូជាមួយនឹងភាពខុសគ្នាជាក់លាក់

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

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}
96

កូដចាវ៉ាដើម្បីរកផលបូកអតិបរមានៃគូជាមួយនឹងភាពខុសគ្នាជាក់លាក់

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា 

O (NlogN), នេះគឺដោយសារតែយើងបានតំរៀបអារេដំបូង។ ហើយបញ្ចូលគ្នាតម្រៀបនិងក្បួនដោះស្រាយតម្រៀបផ្សេងទៀតអាចតម្រៀបអារេនៅក្នុងអូ (NlogN) ។ ប្រសិនបើយើងត្រូវបានផ្តល់ឱ្យនូវធាតុបញ្ចូលដែលបានតម្រៀបយើងអាចដោះស្រាយបញ្ហាបានតាមពេលវេលា O (N) ។

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

O (N), ចន្លោះនេះត្រូវបានទាមទារសម្រាប់ការតម្រៀបអារេ។ ទោះបីយើងមិនបានធ្វើអាដាប់ធ័រ DP ក៏ដោយហើយនឹងប្រើអារេបញ្ចូលដូចគ្នានឹងតារាង DP ដែរ។ ដំណោះស្រាយនោះនៅតែមានភាពស្មុគស្មាញក្នុងចន្លោះដដែលពីព្រោះចន្លោះនេះទាមទារសម្រាប់ការតម្រៀប។