Algoritmdan nazorat savollariga javoblar Algoritm nima

3 5. Eng uzun umumiy qism ketma-ketlik masalasi.

LCS(ABAGTA, AABTA) = LCS(ABAGT, AABT)+1



LCS(ABAGTA, AABTAH) = MAX(LCS(ABAGT, AABTAH), LCS(ABAGTA, AABTA))

• 
   
  

len[i][0] = 0, len[0][j] = 0; boshlang’ich holat




36. Eng uzun o’suvchi qism ketma ketlik masalasi

• 
  a1,a2, … an massiv berilgan. Unda uchraydigan eng katta uzulkidagi o’suvchi qism ketma-ketlikni topish talab etiladi.
  
• 
  Longest increasing subsequence (LIS)
  

Barcha qism ketma-ketliklarni ko’rib chiqish

• 
  n<=20 uchun qo’llash mumkin;
  
• 
  1 2 3 ketma ketlik uchun:
  
• 
  1
  
• 
  2
  
• 
  3
  
• 
  1 2
  
• 
  1 3
  
• 
  2 3
  
• 
  1 2 3
  

Dinamik dasturlash orqali

• 
  Dastlabki i ta son uchun masalani yechamiz. Qism masala sifatida a1,a2, … aj massivni olamiz. i qism masalaga ajratish
  

int dp[n+1];

for (int i = 1; i <= n; i++) {

dp[i] = 1;

for (int j = 1; j < i; j++) {

if (a[j] < a[i] && dp[j]+1 > dp[i])

dp[i] = dp[j] + 1;

}

}

Javobni tiklash

int ans = 0;

for (int i = 1; i <= n; i++) {

if (dp[i] > ans)

ans = dp[i];

}