ការបន្តយូរបំផុតដូចជាភាពខុសគ្នារវាងការនៅក្បែរគ្នាគឺមួយ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon អាវ៉ាតារ៉ា រោងចក្រ Fourkites ក្រុមហ៊ុន Microsoft
អារេ ការសរសេរកម្មវិធីឌីណាមិក លីស។

បញ្ហា“ ការបន្តបន្ទាប់វែងបំផុតភាពខុសគ្នារវាងការប្រាសចាកសីលធម៌គឺជារឿងមួយ” ដែលអ្នកត្រូវបានផ្តល់ឱ្យ integer អារេ។ ឥឡូវអ្នកត្រូវរកប្រវែងនៃការបន្តវែងបំផុតដូចជាភាពខុសគ្នានៃធាតុនៅជាប់គ្នាគឺ ១ ។

ឧទាហរណ៍

ការបន្តយូរបំផុតដូចជាភាពខុសគ្នារវាងការនៅក្បែរគ្នាគឺមួយ

1 2 3 4 7 5 9 4
6

ការពន្យល់

ដូចដែលយើងអាចឃើញថាមានពីរជាបន្តបន្ទាប់ដែលធ្វើតាមលក្ខខណ្ឌ។ ពួកគេគឺ {១, ២, ៣, ៤, ៥, ៤} ហើយម្នាក់ទៀតគឺ {៧,៨} ។ ដូច្នេះការបន្តយូរបំផុតគឺទីមួយ។ ដូច្នេះចម្លើយគឺ ៦ ។

វិធីសាស្រ្តសម្រាប់ការបន្តវែងបំផុតដូចជាភាពខុសគ្នារវាងការនៅក្បែរគ្នាគឺមួយ

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

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

លេខកូដ

លេខកូដ C ++ សម្រាប់ការបន្តវែងបំផុតដូចជាភាពខុសគ្នារវាងការនៅជាប់គ្នាគឺមួយ

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

int main()
{
    int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
    int n = (sizeof input)/(sizeof input[0]);
    int dp[n];memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(int i=1;i<n;i++){
        for(int j=i;j>=0;j--)
            if(abs(input[i]-input[j]) == 1)
                dp[i] = max(dp[i], dp[j]+1);
    }
    int answer = 0;
    for(int i=0;i<n;i++)
        answer = max(answer, dp[i]);
    cout<<answer;
}
6

កូដចាវ៉ាសម្រាប់ការបន្តវែងបំផុតដូចជាភាពខុសគ្នារវាងការនៅជាប់គ្នាគឺមួយ

import java.util.*;

class Main{
  public static void main(String[] args){
      int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
      int n = input.length;
      int dp[] = new int[n];
      for(int i=1;i<n;i++)dp[i] = 0;

      dp[0] = 1;
      for(int i=1;i<n;i++){
          for(int j=i;j>=0;j--)
              if(Math.abs(input[i]-input[j]) == 1)
                  dp[i] = Math.max(dp[i], dp[j]+1);
      }
      int answer = 0;
      for(int i=0;i<n;i++)
          answer = Math.max(answer, dp[i]);
      System.out.print(answer);
  }
}
6

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

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

O (N ^ ២), ពីព្រោះយើងមានរង្វិលជុំពីរ។ មួយត្រូវបានឆ្លងកាត់លើធាតុទាំងអស់និងមួយផ្សេងទៀតត្រូវបានឆ្លងកាត់លើធាតុទាំងអស់ដែលត្រូវបានឆ្លងកាត់។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាសម្រាប់ក្បួនដោះស្រាយក្លាយជាពហុធា។

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

O (N), ចាប់តាំងពីយើងត្រូវរក្សាទុកលទ្ធផលសម្រាប់ធាតុទាំងអស់ដែលយើងបានឆ្លងកាត់រហូតមកដល់បច្ចុប្បន្ន។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺជាលីនេអ៊ែរ។