ProDeveloperTutorial.com

教程和编程解决方案
菜单
  • Shell脚本
  • 系统设计
  • Linux系统编程
  • 4g LTE
  • 编码问题
  • C
  • C ++
  • DSA
  • GIT

动态编程:最长递增子序列

前开发者教程 2020年3月29日

在本教程中,我们将研究最长的递增子序列,并使用动态编程来解决。

 

问题陈述:

给你一个整数数组;您需要找到最长的递增子序列。

这意味着,您需要找到一个排序后的子数组,其总和为max。

 

例:

6_Longest_increasing_subsequence-min

输出:

 

7_Longest_increasing_subsequence-min

这里的长度是4。

这里1、2、5、8在数组中按排序顺序。

还有3、8。但是总和较少。

 

因此,我们将在动态编程的帮助下解决此示例。

我们将采用以下临时数组

8_Longest_increasing_subsequence-min

至少现在,每个索引的最长子序列可以为1。因为,如果数组中没有递增的子序列,则每个索引本身都可以是一个子序列。

 

因此,我们最初在所有索引处用全1填充了DP数组。

9_Longest_increasing_subsequence-min

为了解决这个问题,我们采用2个变量“ i”和“ j”。其中“ i”从索引[1]开始,“ j”从0开始至“ i”。

 

现在,我们检查array [j]上的值是否小于array [i]上的值,然后在DP表中执行一个操作,然后递增索引“ j”。

 

如果arr [j]的值大于arr [i]的值,则我们不对DP数组执行任何操作,只需增加索引“ j”即可。

 

当“ j”和“ i”达到相同的索引时,我们将“ i”值递增以指向下一个元素,并将“ j”值重置为0。

 

再一次,我们继续上一步。

我们将借助一个例子来理解这一点。

 

通行证1:

初始“ i”和“ j”值如下所示

10_Longest_increasing_subsequence-min

 

在此,“ j”为i以上。因此增加“ j”。但是,“ i”和“ j”在同一索引中。因此,我们将“ j”重置为0并增加“ i”值,如下所示:

11_Longest_increasing_subsequence

现在是arr [j]<arr [i]。因此,在dp [i]处最长的递增子序列将是dp [j] +1。

因此它将是dp [2] = dp [0] + 1

dp [2] = 1 +1

dp [2] = 2

12_Longest_increasing_subsequence-min

 

现在增加“ j”值。现在也是arr [j]< arr[i].

因此dp [i] = dp [j] +1

= 1 + 1

13_Longest_increasing_subsequence-min

 

现在增加“ j”,现在“ i”和“ j”的索引都相同。因此,将“ i”增加1并将j值重置为0。

14_Longest_increasing_subsequence-min

 

现在是arr [j]is not less than arr[i]. Hence increment “j”.

 

现在是arr [j]<arr [i]。因此dp [i] = dp [j] +1

= 1 + 1 = 2

15_Longest_increasing_subsequence-min

 

增量j。现在arr [j] = 6且arr [i] =2。arr [j]不小于arr [i]。因此增加“ j”。现在,“ i”和“ j”处于相同的索引。递增“ i”值,将j值重置为0。

16_Longest_increasing_subsequence-min

 

现在arr [j] = 3 ad arr [i] = -1,这不少。同样,所有值都大于arr [i]。因此,我们在此阶段不执行任何操作。

 

下一遍将开始,如下所示:

17_Longest_increasing_subsequence-min

 

如果观察PD阵列,它将始终显示最长增加子序列,直到该索引为止。

 

现在是arr [j]= 3 and arr[i] = 5. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 1 + 1 = 2

 

同样,arr [j] = 1且arr [i] =5。它小于arr [i]。因此,更新DP阵列。

dp [i] = dp [j] + 1

= 1 + 1 = 2

 

同样,arr [j] = 6和arr [i] =5。它大于arr [i]。递增“ j”索引。

 

同样,arr [j] = 2和arr [i] =5。它小于arr [i]。因此,更新DP阵列。

dp [i] = dp [j] + 1

= 2 + 1 = 3

 

同样,arr [j] = -1和arr [i] =5。它小于arr [i]。因此,更新DP阵列。

dp [i] = dp [j] + 1

= -1 + 1 = 0

 

这里我们取最大值[2,2,3,0]。最大值为“ 3”。

在传递结束时,DP阵列将如下所示:

18_最长_递增_子序列

 

再次进行下一次遍历,变量将如下所示:

 

19_Longest_increasing_subsequence-min

 

现在是arr [j]= 3 and arr[i] =4. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 1 + 1 = 2

 

现在是arr [j]= 1 and arr[i] =4. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 1 + 1 = 2

 

现在arr [j] = 6和arr [i] = 4。大于arr [i]。不执行任何操作,将索引“ j”递增。

 

现在是arr [j]= 2 and arr[i] =4. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 2 + 1 = 3

 

现在是arr [j]= -1 and arr[i] =4. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 1 + 1 = 2

 

现在arr [j] = 5和arr [i] = 4。大于arr [i]。不执行任何操作,将索引“ j”递增。

 

在此过程结束时,DP阵列将如下所示:

20_Longest_increasing_subsequence

 

在下一遍的开始,要点如下:

21_Longest_increasing_subsequence

 

现在是arr [j]= 3 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 1 + 1 = 2

 

现在是arr [j]= 1 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 1 + 1 = 2

 

现在是arr [j]= 6 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 2 + 1 = 3

 

现在是arr [j]= 2 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 2 + 1 = 3

 

现在是arr [j]= -1 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= -1 + 1 = 0

 

现在是arr [j]= 5 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 3 +1 = 4

 

现在是arr [j]= 4 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.

dp [i] = dp [j] + 1

= 3 +1 = 4

 

最大值是4,因此是我们的结果。

 

22_Longest_increasing_subsequence

 

C ++解决方案

 

#include<iostream>  
using namespace std; 
    
int dp_function( int arr[], int n )  
{  
    int dp_array[n]; 
   
    dp_array[0] = 1;    

    for (int i = 1; i < n; i++ )  
    { 
        dp_array[i] = 1; 
        for (int j = 0; j < i; j++ )   
            if ( arr[i] > arr[j] && dp_array[i] < dp_array[j] + 1)  
                dp_array[i] = dp_array[j] + 1;  
    } 
      return *max_element(dp_array, dp_array+n); 
}  
    
int main()  
{  
    int arr[] = { 3, 1, 6, 2, -1, 5, 4, 8 };  
    int n = sizeof(arr)/sizeof(arr[0]);  
    printf("Length of Longest Increasing Subsequence is %d\n", dp_function( arr, n ) );  
  
    return 0;  
}

该网站上可用的教程列表:

C编程20+章C ++编程80+章
100多个编码问题数据结构和算法85+章
系统设计20+章Shell脚本编写12章
4g LTE 60+章节最常见的编码问题
5G NR 50+章Linux系统编程20+章

 

分享
电子邮件
鸣叫
领英
Reddit
绊倒
Pinterest的
上一篇文章
下一篇

关于作者

前开发者教程

每天我们都会讨论竞争性编程问题,请加入我们的网站:   电报频道

ProDeveloperTutorial.com

教程和编程解决方案
版权© 2020 ProDeveloperTutorial.com
从以下课程获得热门课程: 教育性的
  • <abbr id="uY1FzfZ"><nav id="gOv2lGT"></nav></abbr>
    <del id="zpD3Bgo"></del>
    <address id="P344O43"><section id="lXkxyn9"></section></address>

    <bdo class="Zw8unsz"><video id="X5Ow0NY" class="X3NuPwx"></video></bdo>


      <textarea id="rgtNqIJ" class="rW97F6h"><dir class="yI3PFdx"><s id="vx0EKgR" class="vP0rpkW"></s></dir></textarea>
      <b class="T0v7vvu"><abbr id="HiYVW1a"></abbr></b>